Python 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. Python Program & output to find and count palindromes between two intervals

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

# initialize
count = 0
# take input of the intervals
ll = int(input("Enter the lower limit = "))
ul = int(input("Enter the upper limit = "))

print("Palindromes between", ll, "and", ul, ": ")
for i in range(ll, ul + 1):
# 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:
print(i, end=" ")
count += 1

# display total no of palindromes
print("\nTotal no of palindromes =", count)


Output

Enter the lower limit = 1

Enter the upper limit = 100

Palindromes between 1 and 100:

1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99

Total no of palindromes = 18