Project Euler 4 - Largest palindrome product

Question

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());
 }
}

Answer 1

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.

• BenKoshy: 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.