Palindrome program

Question

Given a beginning and ending point, check how many numbers are palindromic.

My solution is a bit clunky. How could it be more elegant?

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Palindrome {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter starting point: ");
        int start = sc.nextInt();

        System.out.println("Enter finishing point: ");
        int finish = sc.nextInt();

        List<Integer> numbers = new ArrayList<Integer>();
        int count = 0;

        for (int i = start; i <= finish; i++) {
            numbers.add(i);
            if(isPalinDrome(i)){
                count++;
            }
        }

        System.out.println("[Start value: " + start + "] [End value: " + finish + "] [Number of PalinDromes: " + count + "]");

    }

    public static boolean isPalinDrome(int n){
        String str = Integer.toString(n);
        String reverse = new StringBuilder(str).reverse().toString();

        return str.equals(reverse);
    }

}

Answer 1

It's good that you're aware of Stringbuilder's reverse, but let's try to consider the cost of all these mutations.

As it is, before you even begin checking for the palindromic case, to reverse an integer, you're:

• Changing it to it to a string

• Passing that string to a new stringbuilder

• Using stringbuilder's reverse() method, which loops through the string character by character
• Changing the result of all this back to a string.
• Extracting the reverse logic, which would be a good practice, could even mean changing all this string back to an integer.

This method as a general purpose reverse is fine, but our problem scope here deals only with integers, why not also consider implementing a solution dealing strictly with integers?

Reversing an integer can be done by dividing out remainders of 10 until the number is 0. Making sure to multiply the result by 10, before adding additional remainders so it "moves one place."

Let's see this exemplified, take any number, I'll choose 925 for simplicity's sake:

925 % 10 -> 5
925 / 10 -> 92
92 not 0 -> continue

5 * 10 -> 50
92 % 10 -> 2
50 + 2 -> 52
92 / 10 -> 9
9 not 0 -> continue

52 * 10 -> 520
9 % 10 -> 9
520 + 9 -> 529
9 / 10 -> 0
0 -> end

So, turning this to code, to reverse an integer:

public static int reverse(int n) {
  int reversed = 0;   

   while (n != 0) {
     reversed *= 10;
     reversed += (n % 10);
     n /= 10;
  }

  return reversed;
}

Do note that unlike your current implementation this actually can deal with negative integers without throwing exceptions.

Of course your palindrome method is now simply:

public static boolean isPalindromic(int n) {
    return n == reverse(n);
}

Keep in mind through overloading you can still keep your current method, simply adjusting it purely towards string palindromes. I'd call it a good practice to also extract the reverse logic into its own method however, such would mean your program structure follows the separation of concerns.

Answer 2

numbers seem unused, is that expected?

The palindromic check looks ok to me, but whether you want to inline it altogether is up to you :)

public static boolean isPalinDrome(int n){
    final String str = Integer.toString(n);
    return str.equals(new StringBuilder(str).reverse().toString());
}

If by 'clunky', you are referring to how you are doing the looping in your main method, then you can extract that into its own method too, something like:

private static int countPalindromicValues(int start, int endClosed) {
    ...
}

You should sanity check your inputs too, for negative values or start being larger than finish. This is how I might roll:

int first = scanner.nextInt();
int second = scanner.nextInt();
assert first > 0;
assert second > 0;
for (int i = Math.min(first, second); i <= Math.max(first, second); i++) {
    ...
}

Oh yeah, if you're on > Java 7, remember to use try-with-resources on your Scanner instance.

Answer 3

It looks good to me honestly. Your variable names are good, the flow of your program is logical and well laid out and your isPalinDrome function makes sense. You could improve performance a bit but mlayfman has covered that.

Just a couple of very minor comments. The D in "isPalinDrome" shouldn't really be capitalized, but that's very minor.

Also, your array "numbers" doesn't seem to do anything. You add the value of i to it each loop, but then you don't use it for anything later on in the program.

Answer 4

While your solution works, it is indeed clunky and slow. If I gave as an input a lower bound of say 0 and an upper bound of say 1,000,000,000, your solution would eat up memory for no reason and take ages.

A simple cleanup for memory usage is to get rid of the unused numbers list.

As for algorithm... you are brute forcing every number between the upper and lower limit. Generally you want to find if there is a way of finding just the numbers you want.

A palindrome has the same front half and back half, which means that if we know the first 3 digits are 123 and we are looking for a 5 digit palindrome, we know that the answer is 12321, so we don't need to check all 100 possibilities.

Using this idea, we can approach this problem by counting only the front half, and create the possible numbers by mirroring.

eg. 123 -> 12321, 123321,

Now instead of checking a billion numbers for my crazy test case, you only count around 20000 or so (as there are 10000 possible front halfs, and 2 ways to mirror each front half).