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

Python Program to Find and Count the Palindromes between Two Intervals

in ,
Palindrome

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





Labels: ,