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

Java Program to Find and Count the Palindromes between Two Intervals

in ,
Palindrome

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

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

import java.util.Scanner;

class Main {
    public static void main(String args[]) {
        // declare object of Scanner class
        Scanner sc = new Scanner(System.in);
        // declare variables
        int n, m, revnum = 0, r, count = 0, ul, ll, i;

        // take input of the intervals
        System.out.print("Enter the lower limit = ");
        ll = sc.nextInt();
        System.out.print("Enter the upper limit = ");
        ul = sc.nextInt();

        System.out.println("Palindromes between " + ll + " and " + 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) {
                System.out.print(i + " ");
                count++;
            }
        }
        // display total no of palindromes
        System.out.print("\nTotal no of palindromes = " + count);
    }
}

Output

Enter the lower limit = 100

Enter the upper limit = 500

Palindromes between 100 and 500:

101 111 121 131 141 151 161 171 181 191 202 212 222 232 242 252 262 272 282 292 303 313 323 333 343 353 363 373 383 393 404 414 424 434 444 454 464 474 484 494

Total no of palindromes = 40




Labels: ,