Optimizing the largest palindrome from product of two three digit numbers?

Question

I am working on an interview question which I was asked in which I was supposed to write a program to find the largest palindrome from product of two three digit numbers.

Here is the question

I came up with this brute force approach which starts from bottom.

public class LargestPalindromeQuestion {

    public static void main(String[] args) {
        int value = 0;
        for (int i = 100; i <= 999; i++) {
            for (int j = i; j <= 999; j++) {
                int value1 = i * j;
                if (isPalindrome(value1) && value < value1) {
                    value = value1;
                }
            }
        }
        System.out.println(value);
    }

    private static boolean isPalindrome(final int product) {
        int p = product;
        int reverse = 0;
        while (p != 0) {
            reverse *= 10;
            reverse += p % 10;
            p /= 10;
        }
        return reverse == product;
    }
}

They asked me what are the optimizations I can do in this program? I mentioned that we can try pruning the search space and optimize checking step for each item in the search space but then I am confuse how would I make this work in my above solution?

What are the optimizations we can do in this program? Right now it is executing 810000 steps to find the largest palindrome.

What is the least number of steps we can execute to find the largest palindrome in two three digit numbers?

Answer 1

The program looks very good to me. I would make the i loop count from 999 down to 100, and I would only check j values that would actually give a larger product than the current maximum.

This program is able to finish surprisingly soon, at i == 952 to be precise. The mathematical reason for this is that once the solution 906609 (993 * 913) is found, it will no longer be possible to find a larger palindrome where the larger factor is less than the square-root of 906609, which is 952.160....

public static void main(String[] args) {
    int value = 0;
    for (int i = 999; i >= 100; i--) {
        int r = value / i;
        if (r >= i) {
            System.out.println("We broke at i = " + i);
            break;
        }
        for (int j = i; j > r; j--) {
            int value1 = i * j;
            if (isPalindrome(value1)) {
                value = value1;
                break;
            }
        }
    }
    System.out.println(value);
}

Answer 2

One pretty simple way of optimizing this would be to simply start with the highest 3-digit numbers instead of the smallest. Since the solution will most likely be closer to the pair (999 , 999) than to (100 , 100).