1
\$\begingroup\$

I submitted a solution to Project Euler 4 exercise: Largest palindrome product in Java. The content of following exercise:

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.

I wrote a method called isPalindrome that checks is reversing of string the same as output string. I have to obviously convert int to String to check is given number is palindrome. I created palindromes list and I loop for all possible three-digits numbers that would be multiplied and I check are these products palindromes. If yes, then I add it product to list. Next, I select only maximum palindrome from list and I print it to console.

Main.java:

package pl.hubot.projecteuler.problem4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> palindromes = new ArrayList<>();
        for (int i = 100; i <= 999; i++) {
            for (int j = 100; j <= 999; j++) {
                if (isPalindrome(Integer.toString(i * j)))
                    palindromes.add(i * j);
            }
        }
        System.out.print(Collections.max(palindromes));
    }

    private static boolean isPalindrome(String str) {
        return str.equals(new StringBuilder(str).reverse().toString());
    }
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

We don't need a List

        List<Integer> palindromes = new ArrayList<>();

This could be just

        int largest = -1;

As we just need to determine the largest one.

        System.out.print(Collections.max(palindromes));

This just becomes

        System.out.print(largest);

Work down, not up

        for (int i = 100; i <= 999; i++) {
            for (int j = 100; j <= 999; j++) {

This does more work than necessary. Instead, consider

        for (int i = 999; i >= 100; i--) {
            for (int j = i; j >= 100; j--) {

You want to find the maximum. So start with the largest possible candidate and work your way down.

Also, you don't have to check \$999\cdot 998\$ and \$998\cdot 999\$. It's enough to test one. So we can start j as i.

There will be more that we can do later.

Convert after calling isPalindrome

                if (isPalindrome(Integer.toString(i * j)))
                    palindromes.add(i * j);

Consider

                int product = i * j;
                if (product <= largest) {
                    break;
                }

                if (isPalindrome(product)) {
                    largest = product;
                }

If product is smaller than the largest palindrome found so far, we don't need to check these values anymore. Also, we only update largest if product is larger. So we don't need to do the Collections.max after.

We don't repeatedly calculate the same product (compiler probably fixes that for you anyway, but I find this easier to follow).

You said

I have to obviously convert int to String to check is given number is palindrome.

But it is not obvious to me that we have to convert to a String to check if it is a palindrome. That's a conceptually simple way, but we could do it more efficiently with math. And this way, we can drop in a math-based replacement without altering this method.

And to fix the mismatched parameters without using a replacement, we could just write

    private static boolean isPalindrome(int candidate) {
        return isPalindrome(Integer.toString(candidate));
    }

And as I said, we can replace that method with a more efficient one without changing the caller.

\$\endgroup\$
1
  • \$\begingroup\$ you've said what i wanted to say and have done it better too! i bookmarked this question to take care of it later. i wonder how it would turn out if i implemented a TDD approach? would be interesting to look at. \$\endgroup\$
    – BenKoshy
    May 2, 2017 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.