Project Euler #4: Largest palindrome product

Question

How can I make my code for Project Euler #4 more efficient and cleaner?

Project Euler #4: Largest palindrome product:

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 class LargestPalindromeProduct {
    public static void main(String[] args) {

        int product = 0;
        int largest = 0;
        for (int first = 1; first < 1000; first++) {
            for(int second = 1; second < 1000; second++) {
                product = first * second;
                if ((product / 100000) % 10 == product % 10 && product / 10000 % 10 == product / 10 % 10 && product / 1000 % 10 == product / 100 % 10) {
                    //System.out.println(product);
                    if (product > largest) {
                        largest = product;


                    }                   
                }

            }
        }
        System.out.println(largest);    
    }
}

Answer 1

For increased performance I think it might make sense to enhance your loop:

1. Start with 999 each and count downwards, as the largest product will most likely involve bigger numbers. This allows you to implement a strategy for pruning and return earlier (see other answers and comments for details).
2. Count only in the range of 100-999, since 1-99 aren't 3-digit numbers.

For a cleaner code you should refactor your if clause into a separate method. Something like

private boolean isPalindrome(int product) {
    return ((product / 100000) % 10 == product % 10
         && (product / 10000) % 10 == (product / 10) % 10
         && (product / 1000) % 10 == (product / 100) % 10);
}

A cleaner code would for me also involve consistent formatting and use of brackets, e.g.

• (product / 100000) % 10 vs product / 10000 % 10
• for (int first = 1 vs for(int second = 1

Answer 2

Consider declaring variables closest to where they're going to be used. I'm talking specifically about the product variable.

Delete

int product = 0;

and instead leave

int product = first * second;

---

Also, you'd benefit from a better use of whitespace to perhaps something like:

public class LargestPalindromeProduct {

    public static void main(String[] args) {
        int largest = 0;

        for (int first = 1; first < 1000; first++) {
            for(int second = 1; second < 1000; second++) {
                int product = first * second;

                if ((product / 100000) % 10 == product % 10 && product / 10000 % 10 == product / 10 % 10 && product / 1000 % 10 == product / 100 % 10) {
                    if (product > largest) {
                        largest = product;
                    }                   
                }
            }
        }

        System.out.println(largest);    
    }

}

---

You can also increase efficiency by checking if the product is larger than largest first, and then checking if product is a palindrome or not.

Answer 3

Consider moving your logic into its own method. That will allow for unit testing as well as manual testing in main.

Consider a method for isPalindrome that does a more general check (not just six digits).

    private static final int BASE = 10;

    public static boolean isPalindrome(int number) {
        int reversed = number % BASE;
        number /= BASE;

        while (number > reversed) {
            reversed *= BASE;
            reversed += number % BASE;

            // check for a palindrome with an odd number of digits
            if (number == reversed) {
                return true;
            }

            number /= BASE;
        }

        return number == reversed;
    }

This pulls off the digits from the end and reverses them into a new number. It checks for equality once after putting a digit into the reversed number and before pulling it off the original. That looks for palindromes with an odd number of digits. Once the number is no longer greater than reversed, it checks again to look for palindromes with an even number of digits.

Or break it up into an int collection of digits and compare from start to finish.

    public static boolean isPalindrome(int number) {
        List<Integer> digits = new ArrayList<>();

        while (number > 0) {
            digits.add(number % BASE);
            number /= BASE;
        }

        for (int start = 0, end = digits.size() - 1; start < end; start++, end--) {
            if (digits.get(start) != digits.get(end)) {
                return false;
            }
        }

        return true;
    }

Conceptually simpler but uses more memory and has the List overhead.

As @Marvin and @Pimgd already said, start at the top and work your way down.

Also, do your product > largest check before the isPalindrome check, as it is cheaper.

    public static int find(int ceiling, int floor) {
        int largest = -1;

        for (int i = ceiling; i >= floor; i--) {
            int product = ceiling * i;
            if (product < largest) {
                // all future products will be smaller than this one
                return largest;
            }

            int squared = i * i;

            // if they are large enough to be an answer,
            // we'll check products smaller than i * i later
            // we never need to check products smaller than largest
            int minimum = Math.max(squared, largest);
            do {
                if (isPalindrome(product)) {
                    largest = product;
                    minimum = Math.max(squared, largest);
                }

                product -= i;
            } while (product >= minimum);
        }

        return largest;
    }

Now we don't have to multiply on each iteration of the inner loop to get product, we multiply once and then decrement from the product.

Then your main would be simpler:

    public static void main(String[] args) {
        System.out.println(LargestPalindromeProduct.find(999, 100));
    }

This would also allow you to set up unit tests. For example, you might check that LargestPalindromeProduct.find(99, 10) is 9009.

Answer 4

Start from 999. When the highest of first and second multiplied by itself is smaller than the palindrome you've already found, then you're done. This should cut off quite a significant portion of the time spent.

Answer 5

You can make some optimizations in your for loop. You can count downwards as you are going to find the largest palindrome with the bigger numbers.

You don't need to repeat combinations, e.g., if you test with 999 x 998, you don't need to check again with 998 x 999.

So far, the loop could be:

for (int first = 999; first >= 100; first--) {
    for(int second = first; second >= 100; second--) { // Initialize second to first to skip repetitions.
        ...
    }
}

You don't need to iterate over all the possible values, at some point you are not going to find a largest result. Also, the first palindrome found is not the largest one. e.g. 580085 (995x583) is the first one but it is not the max. 906609 (993x913) is the correct result and it is found later. The iteration can be stopped when the products are lower than the largest palindrome found so far.

int maxPalindrome = -1;
for (int first = 999; first >= 100; first--) {
    if (first * first < maxPalindrome) {
        break;
    }
    for(int second = first; second >= 100; second--) { // Initialize second to first to skip repetitions.
        int product = first * second;
        if (product < maxPalindrome) {
            break;
        }
        if (isPalindrome(product)) {
            maxPalindrome = product;
        }
    }
}

Answer 6

Your code is no doubt correct but really tedious during implementation. I would like to suggest an alternative approach to make your code more efficient in terms of both length and optimizations.

Alternative Approach

I was surprised that nobody used String Handling as an approach to solve the question, Which happened to be my first idea (Probably because you did not explicitly ask for an alternative approach).

According to the input data and complexity of the problem it can be judged that any good algorithm should compute it within 1-2 secs which is why all the Answers (not the code in question itself) are equally good options/ suggestions.

The main highlight of my approach which makes it different is the use of StringBuilder and reverse() to save myself from the hassles of actually computing the palindrome. I believe this makes the code smarter, shorter and less tedious to implement.

As rightly pointed out in comments I believe it hardly matters if I start from 100 or 999 because in any case I have to go through all cases, but do take care about how repetitions are ignored.
Good Luck!

---

class Euler4 {
    public static void main(String args[]) {
        int largest = 0;

        for(int num1 = 100; num1 < 1000; num1++){
            for(int num2 = num1; num2 < 1000; num2++){
                int product = num1 * num2;
                //The next if statements saves time by ignoring many cases
                if(product > largest){
                 String str1 = Integer.toString(product);
                 //Single step to reverse num1
                 String str2 = new StringBuilder(str1).reverse().toString();
                 if(str1.equals(str2)) largest = product;
                }
            }
        }

        System.out.println(largest);
    }
}