5
\$\begingroup\$

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);    
    }
}
\$\endgroup\$
  • \$\begingroup\$ @Marvin sounds like an answer \$\endgroup\$ – Pimgd Jul 6 '16 at 22:47
  • 2
    \$\begingroup\$ You're trying out both 123 * 124 and 124 * 123 (for example). There's no need to try both. \$\endgroup\$ – Michael Shaw Jul 6 '16 at 23:03
  • 2
    \$\begingroup\$ Your code is incorrect when the product is less than six digits. For example a product 1221 is a palindrome, but will not pass your test. Assuming that there is a six digit palindrome product, this won't matter. \$\endgroup\$ – gnasher729 Jul 7 '16 at 8:21
7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Out of curiosity - why do you consider counting downwards better? You'll still have to check every combination [(a,b) | a <- [100, 999], b <- [100, 999], a < b ] (unless you perform some clever pruning where you exclude all b with b * 1000 < currentMax). \$\endgroup\$ – Frank Schmitt Jul 7 '16 at 7:24
  • 1
    \$\begingroup\$ Exactly. You do perform some clever pruning. Once you found a palindrome, you don't check any smaller product whether it is a palindrome, since you know it's not the largest palindrome. And given a, you start with the smallest b that makes a * b larger than the largest palindrome so far. And once you have an a where 999a <= largest palindrome, you stop. For three digit numbers that makes no difference. But try nine digit numbers. \$\endgroup\$ – gnasher729 Jul 7 '16 at 8:18
  • 1
    \$\begingroup\$ @FrankSchmitt: Yes - I was thinking about pruning, but didn't mention it. I added a note, thanks! \$\endgroup\$ – Marvin Jul 7 '16 at 18:52
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

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);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.