## Project Euler Problem 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 palidrome made from the product of two 3-digit numbers.

You can find my full solution here.

Before we get too ahead of ourselves, let’s define the problem.

The problem wants us to find if two numbers (ranging from 1 to 999) multiplied together creates a palindrome. A palindrome is something that reads the same forwards and backward. For example, wow and racecar are examples of palindromic words. Some palindromic numbers would be 3223 or 4444.

To solve this problem, we want to multiply two numbers. Then, we can reverse the product and see if it equals the original product. We could do this simply by turning the number into a string and reversing it.

We’ll have a variable that indicates the largest palindrome we’ve found so far, and if a new palindrome is found and it’s bigger than the largest one so far, we’ll change the largest palindrome variable to the new largest palindrome.

At the end of the program, we can simply print out the largest palindrome we have so far.

Let’s start implementing our ideas in code!

## Coding a Solution

Let’s stub out an application where we can store all of our code.

public class Euler4 {
static final int MAX = 999;
public static void main(String[] args) {

}
}

The static final int member represents the largest number any one of our products can be, in this case, the problem asks us to multiply two three-digit numbers so the largest number is 999.

Now, we need to multiply every single number between 1 and 999 by every single number between 1 and 999. This would be a good time to use two nested for loops.

public class Euler4 {
static final int MAX = 999;
public static void main(String[] args) {
int largestPalindromeProduct = 0;
for(int i = 1; i <= MAX; i++) {
for(int j = 1; j <= MAX; j++) {
int product = j * i;
}
}
}
}
}

I also defined a few local variables above: largestPalindromeProduct will hold the current largest palindrome we’ve found, and the product integer within the nested for loops will hold the product of the two integers.

Now, all that’s left to do is check if these numbers are the same backward and forwards, and update the largestPalindromeProduct accordingly.

There are a number of ways you could do this in code, but one way to do it in Java is to turn the number into a string, reverse that string, and check that value against the original string.

public class Euler4 {
static final int MAX = 999;
public static void main(String[] args) {
int largestPalindromeProduct = 0;
for(int i = 1; i <= MAX; i++) {
for(int j = 1; j <= MAX; j++) {
int product = j * i;
String productString = String.valueOf(product);
StringBuilder productReversed = new StringBuilder();
productReversed.append(productString);
productReversed.reverse();
if(productReversed.toString().equals(productString) && product > largestPalindromeProduct) {
largestPalindromeProduct = product;
}
}
}

System.out.println(largestPalindromeProduct);
}
}

In the above code – this is also the final code for the program – I’ve added the logic I described previously. Strings don’t have a reverse method built into them, but we can create a StringBuilder and reverse that. To do that, we declare a new instance of StringBuilder and append to it the string representation of the product of the two numbers.

Then, we can reverse that string with the reverse() method. Now that our string has been reversed, we can check that string against the string that isn’t reversed. If the string is the same backward and forwards, and the product is greater than the currently defined greatest palindrome, we set the largestPalindromeProduct variable to the product.

Finally, we can get our answer by printing the largestPalindromeProduct after every combination of numbers have been tried.