Home / C / Loop / C Program to Find and Count the Palindromes between Two Intervals

C Program to Find and Count the Palindromes between Two Intervals

in ,
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
***********************************/

#include <stdio.h>

int main() {
    // declare variables
    int n, m, revnum = 0, r, count = 0, ul, ll, i;

    // take input of the intervals
    printf("Enter the lower limit = ");
    scanf("%d", & ll);
    printf("Enter the upper limit = ");
    scanf("%d", & ul);

    printf("Palindromes between %d and %d: \n", ll, 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) {
            printf("%d, ", i);
            count++;
        }
    }
    // display total no of palindromes
    printf("\nTotal no of palindromes = %d", count);

    return 0;
}

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 = 1000

Enter the upper limit = 1500

Palindromes between 1000 and 1500:

1001, 1111, 1221, 1331, 1441,

Total no of palindromes = 5





Labels: ,