5
\$\begingroup\$

I'm kinda new to Java (<1 year) but have some background in C and Python.

I've come up with a working solution to Project Euler Problem 4 - Largest Palindrome Product. However, I'm not confident this is "Effective Java"...

All suggestions for improvement are welcome. I'd especially like feedback on the following:

  • Java language usage
  • Java library usage
  • Algorithm performance

/**
 * Palindrome Integer is a whole number which reads the same both ways.
 */
public class PalindromeInteger {

    /**
     * Predicate to determine whether the given number is a palindrome.
     * @param integer
     * @return true if palindrome, false otherwise.
     */
    public static boolean isPalindrome(int integer) {
        String integerStr = String.valueOf(integer);
        StringBuilder sb = new StringBuilder();
        sb.append(integerStr);
        String integerStrReversed = sb.reverse().toString();
        return integerStrReversed.equals(integerStr);
    }

    /**
     * Returns a Set of the palindrome integers which can be made from the product of the given integers.
     * @param multiplicand
     * @param multiplier
     * @return a Set of palindrome integers.
     */
    public static Set getPalindromeProducts(int multiplicand, int multiplier) {
        Set palindromes = new HashSet();
        for (int i = multiplicand; i >= 0; i--) {
            for (int j = multiplier; j >= 0; j--) {
                int product = i * j;
                if (isPalindrome(product))
                    palindromes.add(product);
            }
        }
        return palindromes;
    }

    /**
     * Returns the largest Palindrome integer possible from the product of the two given integers.
     * @param multiplicand
     * @param multipler
     * @return palindromic integer e.g. 9009
     */
    public static int getLargestPalindromeProduct(int multiplicand, int multipler) {
        Set palindromes = getPalindromeProducts(multiplicand,
                multipler);
        return (int)Collections.max(palindromes);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ StringBuilder has a constructor that takes a string as an argument. This could've saved you a line, but isn't really important. Also, you need to parametrize the methods, this would have saved you a C-style cast in the last method (compiler would be able to infer which overload of Collection.max to use). \$\endgroup\$ – wvxvw Mar 23 '15 at 16:40
5
\$\begingroup\$

Your method isPalindrome produces wrong results for negative numbers. (which is not important for Project Euler #4, but still) It is also inefficient to convert all numbers to String. I would only do that when using BigInteger. With int, you can just use a little math:

public static boolean isPalindrome(int number) {
    return number == reverse(number);
}

public static int reverse(int number) {
     //negative numbers: reverse the positive and negate it again.
    if (number < 0) return -reverse(-number);
    //a 1-digit number is its own reverse
    if (number < 10) return number;
    int reversed = 0;
    while (number > 0) {
        //take the last digit of number and paste it to reversed.
        reversed = reversed * 10 + number % 10;
        //cut off the last digit
        number /= 10;
    }
    return reversed;
}

You are not using the method getPalindromeProducts(int multiplicand, int multiplier) correctly. You run both loops all the way down to zero.
The meaning of the names multiplicant and multiplier isn't clear imo. In a multiplication, both numbers are just factors. One of them is the minimum (100) and the other is the maximum (999). You're looking for numbers between 100 and 999, not between 100 and 0 or between 999 and 0.
You also do a lot of the work twice by running both loops all the way. For example, you will get a * b AND b * a. You can skip a lot of iterations by breaking out of the loop early.

Another thing to think about is the HashSet. The problem with Java Collections is that you cannot use them with primitive types. It will convert all numbers to Object, which will hurt performance. (You cannot have a HashSet<int> for example)
However, in this case, you don't need a HashSet at all. You don't care about duplicates, you just want to find the largest product. It is also not necessary to store all the palindromes you found; you only need the largest one.

public static int getLargestPalindromeProduct(int minFactor, int maxFactor) {
    int largest = 0;
    for (int a = maxFactor; a >= minFactor; --a) {
        for (int b = maxFactor; b >= a; --b) {//Note the b >= a, not b >= minFactor
            int product = a * b;
            if (product <= largest) break; //We can stop this iteration, because factors will only get smaller.
            if (isPalindrome(product)) {
                largest = product;
                break;
            }
        }
    }
    return largest;
}

Then call getLargestPalindromeProduct(100, 999);

\$\endgroup\$
1
\$\begingroup\$

Since I am not a Java programmer I will just comment on the core algorithm here. I am not sure if there is a non-naive solution to this problem so I will focus on the naive approach.

  • We start at the top end of the range, that is with operands a and b equal to 999.
  • We can dynamically change the ranges of our operands a and b instead of exploring the entire solution set.

To accomplish the dynamic range we need to have a strict ordering. Here I will always assume \$b \geq a\$

int min_factor = 99;
int max_product = 0;

for(int b = 999; b > min_factor; b--)
{
    for(int a = b; a > min_factor; a--)
    {
        int c = a * b;
        if(is_palindrome(c))
        {
            min_factor = a;

            if(c > max_product)
            {
                max_product = c;
            }
        }
    }
}

The principle of the dynamic range here is that if we have some palindrome \$a_1 \cdot b_1\$ already and we are trying to find another palindrome \$a_2 \cdot b_2\$ such that \$ a_2 \cdot b_2 \gt a_1 \cdot b_1\$ where \$b_2 < b_1\$ then that implies \$a_2 > a_1\$.

You can add a break condition if(c < max_product) as Dennis does however you will find it doesn't have much affect on this algorithm unless the palindromes are sparse.

\$\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.