Checking a numeric palindrome

Question

Given A and B, count the numbers N such that A ≤ N ≤ B and N is a palindrome.

Input:

First line contains T, the number of testcases. Each testcase consists of two integers A and B in one line.

Output:

For each testcase, print the required answer in one line.

Constraints:

1 ≤ T ≤ 10

0 ≤ A ≤ B ≤ 10^5

private static boolean[] isPalindrome = isPalindrome();
    public static void main(String args[] ) throws NumberFormatException,
IOException{
       BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        int totalTestCase = Integer.parseInt(reader.readLine());
        StringBuilder outputPalindromeCount = new StringBuilder();
        for (int i = 0; i < totalTestCase; i++) {
            String[] input=reader.readLine().split(" ");
            int startNo = Integer.parseInt(input[0]);
            int endNo = Integer.parseInt(input[1]);
            int totalFoundPalindrome = getPalindromeCount(startNo, endNo);
            outputPalindromeCount.append(totalFoundPalindrome + "\n");
        }
        System.out.println(outputPalindromeCount);

    }

    private static int getPalindromeCount(int startNo, int endNo) {
        int totalPalindromeFound = 0;
        for (int i = startNo; i <= endNo ; i++ ){
            if(isPalindrome[i]){
                totalPalindromeFound++;
            }
        }
        return totalPalindromeFound;
    }

    private static boolean[] isPalindrome() {
        boolean[] isPalindrome = new boolean[100001];
        Arrays.fill(isPalindrome, 0, 10, true);
        for (int i = 10; i <= 100000; i++) {
            if (checkForPalindrome(i)) {
                isPalindrome[i] = true;
            }
        }
        return isPalindrome;
    }

    private static boolean checkForPalindrome(int i) {
        int divNo = 1;
        while (i / divNo >= 10) {
            divNo = divNo * 10;
        }

        while (i != 0) {
            int startingDigit = i / divNo;
            int lastDigit = i % 10;
            if (startingDigit != lastDigit) {
                return false;
            }
            i = (i % divNo) / 10;
            divNo = divNo / 100;

        }
        return true;
    }

}

For this input:

6
0 0
1 1
1 10
1 9
1 1000
1000 100000

this code took 0.18 seconds. It's taking almost 0.18-0.20 seconds for various sets of input (link of all inputs and time).

What are the other Efficient way of checking palindromes (not just a way of conversion to a string and then check but really efficient)?

How could have I optimized the above code further (apart from BitSet which is a trade off for runtime)?

janos · Accepted Answer · 2015-06-04 22:09:04Z

isPalindrome is a very unfortunate name in this code:

Names starting with "is" are typically methods returning a simple boolean
... but in this code isPalindrome is a parameterless method returning a boolean array
... and at the same time there is also a boolean array called isPalindrome

It would be better to use different names for the method and the array, and neither should start with the word "is".

In the isPalindrome method, you could shorten this:

        if (checkForPalindrome(i)) {
            isPalindrome[i] = true;
        }

to this:

        isPalindrome[i] = checkForPalindrome(i);

I'm a big fan of descriptive variable names, but I think you went a bit overboard, for example here:

private static int getPalindromeCount(int startNo, int endNo) {
    int totalPalindromeFound = 0;
    for (int i = startNo; i <= endNo ; i++ ){
        if(isPalindrome[i]){
            totalPalindromeFound++;
        }
    }
    return totalPalindromeFound;
}

I would simplify some of the names there to:

private static int getPalindromeCount(int start, int end) {
    int palindromeCount = 0;
    for (int i = start; i <= end; i++) {
        if (isPalindrome[i]) {
            palindromeCount++;
        }
    }
    return palindromeCount;
}

The numbers 100001 and 100000 are magic. It would be good to create a constant from 100000 with a descriptive name.

A small tip: it's a lot easier to parse simple input using a Scanner, with its nextInt and nextLine methods, instead of a BufferedReader and Integer.parseInt.

Also, why build output in a StringBuilder if you will print its contents anyway inside the same method. You could just print the results directly.

mdfst13 · Accepted Answer · 2015-06-04 23:39:54Z

        int divNo = 1;
        while (i / divNo >= 10) {
            divNo = divNo * 10;
        }

        while (i != 0) {
            int startingDigit = i / divNo;
            int lastDigit = i % 10;
            if (startingDigit != lastDigit) {
                return false;
            }

            i = (i % divNo) / 10;
            divNo = divNo / 100;
        }

This seems more complicated than it needs to be. First you are finding the location of the first digit. Then you go through digit by digit. Why not do both at once and get rid of divNo?

    private static boolean isPalindrome(int left) {
        // a trailing zero is impossible to match
        if (left % BASE == 0) {
            // only a literal 0 will work
            return left == 0;
        }

        int right = 0;
        while (left > right) {
            int currentDigit = left % BASE;
            left /= BASE;

            // if there are an odd number of digits,
            // and the left half of the number equals the reversed right half,
            // it's a palindrome
            if (left == right) {
                return true;
            }

            // reverse the right half, assuming no trailing zeroes
            right = BASE * right + currentDigit;
        }

        // if there are an even number of digits
        return left == right;
    }

Note that I also renamed isPalindrome to generatePalindromes and checkPalindrome to isPalindrome. And I added a constant to replace the magic number 10. Algorithm explained inline with comments.

Stack Exchange Network

Checking a numeric palindrome

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Checking a numeric palindrome

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions