Project Euler #4 – Largest Palindrome Product in Java

I am seeing that this is actually not in accord with the difficulty level said there. Firstly I cannot list all possible improvements it could have.

/*
 * A palindromic number reads the same both ways. The largest palindrome
 * made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the
 * largest palindrome made from the product of two 3-digit numbers.
 */
public static int get4() {
    int max = 1;
    for (int i = 100; i < 999; i++) {
        for (int j = i; j < 999; j++) {
            int n = i * j;
            int len = (int) Math.floor(Math.log10(n));
            boolean ispalindrome = true;
            for (int k = 0; k < 3; k++) {// 100^2=10^4,999^2=998001. 5-6
                                            // digits middle atmax 3
                int digitatk = (int) ((n % Math.pow(10, k + 1) - n
                        % Math.pow(10, k)) / Math.pow(10, k));
                // eg. digit at 3 of 12345 =
                // (12345%10^4-12345%10^3)/10^3=(2345-345)/10^3=2000/10^3=2
                int l = len - k;
                int digitatl = (int) ((n % Math.pow(10, l + 1) - n
                        % Math.pow(10, l)) / Math.pow(10, l));
                if (digitatl != digitatk) {
                    ispalindrome = false;
                }
            }
            if (ispalindrome && n > max) {
                max = n;
            }
        }
    }
    return max;
}

Output:

Answer is 906609
Time taken 2.82342934 seconds

Current problems (not exhaustive):

• Time
• ${mathcal O}(n^2)$ where $n=999$ for looping only.
• Length-checking method
• Checking palindrome
• Digit-finding method

Algorithm

Your time and complexity problems are probably the more serious ones. Your code starts small (at 100), and then works up to 1000. This is not the most efficient way of brute-forcing the problem. A better solution would be to start at 999 and work back to 100, but limit it when the result becomes impossible…. let me explain:

    int max = Integer.MIN_VALUE;
    for (int i = 999; i > 100 && i * 999 > max; i--) {
        for (int j = 999; j > i; j--) {
            ....

1. start high (999 x 999)
2. Work backwards from there where the second number is larger than the first
3. track your maximum
4. terminate the loops if the current i (or smaller) values will never beat the maximum.

Using the above logic, you will eliminate a huge number of loops.

Length check & Finding digit

The Log function is a good check for the length of the value, it’s fine. On the other hand, it may not be necessary at all… same applies to the “finding digit”

Palindrome

I like the following method for identifying palindromic numbers:

private static final int reverse(int value) {
    int result = 0;
    while (value != 0) {
        result *= 10;
        result += value % 10;
        value /= 10;
    }
    return result;
}

Using that function, your palindrome check simply becomes:

boolean ispalindrome = n == reverse(n);

There are several improvements that can be made to answer this question. You could start your loop from the largest possible number which is 999 and come down to 100. Once a palindrome is found, you can break. This should increase your speed.

for(int i = 999; i >= 0; i--){
        for(int j = 999; j >=i; j-- ){
            if(isPalindrome(j*i)){
                if(j*i > max)
                max= j*i;
                break;
            }
        }
    }

For your isPalindrome function, you can test different ways to find if a number is a palindrome. You could convert the number to a string and do a string palindrome test.

public static boolean isPal(String s){
  if(s.length() == 0 || s.length() == 1){
      return true;
  }
  if(s.charAt(0) == s.charAt(s.length() -1))
      return isPal(s.substring(1,s.length()-1));
  return false;
}

Basically, if the length is 0 or 1 return true. Then keep checking first and last index recursively. Another way could be basically reversing the number and checking if they are equal.

You don’t want to find all pairs with a palindromic product, only the largest one. So you don’t need to check pairs (i, j) where i*j is less than the largest palindrome that you found so far. But you can take even better advantage of this by checking large products first. And since the order of i and j doesn’t matter, you can assume that i >= j.

int largest_i = 0;
int largest_j = 0;
int largest = 0;

for (int i = 999; i >= 100 && i*i >= largest; --i)
{
    int min_j = largest / i;
    for (int  j = i; i >= min_j; --j)
    {
        if (ispalindrome (i * j))
        {
             largest = i*j;
             largest_i = i;
             largest_j = j;
             break;
        }
    }
}

You could also make a bet that there is most likely a palindrome >= 800,000 and let largest = 800,000 initially. So you would multiply 999 only with numbers from 999 to 801, for example. This would likely be faster again; if it fails to find any palindrome you have to do the full solution.

You could first look for palindromes >= 900,000 then for palindromes >= 800,000 etc. This has the advantage that you know which is the smallest digit, which makes the test faster. And smallest digit = 9 means i and j must both be odd. Last digit = 8 means j must be even if i is odd. Not that important for 3×3 digits, but assume you are asked to check for the largest palindrome from 8 digit numbers…