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.

#### Page content(s):

1. Algorithm

2. Pseudocode

3. Time Complexity

4. Program & Output

## 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