C# Program to Find and Count the Palindromes between Two Intervals

Palindrome

C# program to find and count the palindromes between two intervals has been shown here. For example, the total no of palindromes between $100$ and $200$ is $10$ (i.e. $101, 111, 121, 131, 141, 151, 161, 171, 181, 191$). The following section covers the iterative approach to count the palindromes. The algorithm, pseudocode and time complexity of the program have also been shown below.






1. Algorithm to count palindromes between two intervals


1. Take two intervals as input. Consider ul as upper limit and ll as lower limit.

2. Intialize a counter variable say count = 0 and another variable say i = ll

3. For each number i $\in$[ll, ul]

4. Copy value of i to another variables say n i.e. n = i

5. Initialize a variable to 0 say reverse = 0.

6. Perform r = n % 10.

7. Perform reverse = reverse * 10 + r.

8. Perform n = n / 10

9. If n = 0 go to step 10 else go to step 6.

10. Check If reverse == i

11. If step 10 is true then perform count = count + 1 else do nothing.

12. Perform i = i + 1

13. Check if i <= ll

14. If step 14 is true go to step 3, else stop the process and show count as output.




2. Pseudocode to count palindromes between two intervals


Input : Upper limit $ul$ and lower limit $ll$

Output : Number of palindromes between $ul$ and $ll$

1. Procedure countPalindromes($ul$, $ll$):

2. $count \leftarrow 0$

3. For each i $\in [ll, ul]$

4. $reverse \leftarrow 0$

5. $n \leftarrow i$

6. Repeat until $n \neq 0$

7. $reverse \leftarrow reverse * 10 + (n \mod 10)$

8. $n \leftarrow n / 10$

9. If $reverse == i$:

10. $count \leftarrow count + 1$

11. Return $count$

12. End Procedure





3. Time complexity to count palindromes between two intervals


Time Complexity: O(nlog(n))

Where n is the total no of values between the upper limit and lower limit. To check if a number m is palindrome or not it takes O(log(m)) time.





4. C# Program & output to find and count palindromes between two intervals

Code has been copied
/*********************************
        alphabetacoder.com
C# program to count the number of 
palindromes between two intervals
***********************************/

using System;

namespace Palindromes {
    class Program {
        static void Main(string[] args) {
            // declare variables
            int n, revnum = 0, r, count = 0, ul, ll, i;

            // take input of the intervals
            Console.Write("Enter the lower limit = ");
            ll = Convert.ToInt32(Console.ReadLine());
            Console.Write("Enter the upper limit = ");
            ul = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("Palindromes between " + ll + " and " + ul + ": ");
            for (i = ll; i <= ul; i++) {
                // copy the current number
                n = i;
                // initialize
                revnum = 0;
                //find the reverse
                while (n != 0) {
                    // extract the unit digit
                    r = n % 10;
                    // store the reverse number
                    // give appropriate positional value
                    // of each digit
                    revnum = revnum * 10 + r;
                    //divide the number by 10
                    n = n / 10;
                }
                // check for palindrome
                // if current number is 
                // palindrome increment the counter
                // and show the number
                if (i == revnum) {
                    Console.Write(i + " ");
                    count++;
                }
            }
            // display total no of palindromes
            Console.WriteLine("\nTotal no of palindromes = " + count);

            // wait for the user to press any key
            Console.ReadKey();
        }
    }
}

Output


Case 1:

Enter the lower limit = 100

Enter the upper limit = 200

Palindromes between 100 and 200:

101 111 121 131 141 151 161 171 181 191

Total no of palindromes = 10


Case 2:

Enter the lower limit = 10

Enter the upper limit = 50

Palindromes between 10 and 50:

11 22 33 44

Total no of palindromes = 4