**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.

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

4.

5.

6. **Repeat until **$n \neq 0$

7.

8.

9. **If ** $reverse == i$:

10.

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

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