In this blog post we will be looking at problem 4 of Project Euler and we will program a solution in Java.

The problem of Project Euler found here, below is the problem for quick lookup.

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.

-Project Euler problem 4

Let’s break the problem into some smaller ones:

• We need to be able to know when a number is a palindrome
• We need to loop from 100 to 999 twice to consider all possibilities
• We need to save the largest palindrome

The 2 for loops

It’s actually quite a simple problem. It’s very simple with a nested loop. There might be other ways of doing it but sometimes a simple solution is better than an over engineered solution so let’s just get into it.

We start by declaring a variable named maxResult to hold the largest palindrome, we initialize it to 0. Then we start 2 for loops from 100 to 999 inclusive, one nested inside of the other. Remember, only 3 digit numbers need to be considered. We use the loop counters from these two loops to create a product of two 3-digit numbers and consider it as a palindrome.

Then in the if condition we check if the possible result is higher than the max result, if it is we then check the next condition of the if which is if it is a palindrome. We accomplish this by reversing the digits of the possible result and comparing it against possible result. The function is explained below. If both of these conditions are true it is a palindrome and a higher palindrome so we save it into maxResult.

long maxResult = 0;
for(int i = 100; i <= 999; i++){
    for (int j = 100; j <= 999; j++){
        long possResult = i * j;
        if (possResult > maxResult && possResult == reverseNumber(possResult)){
            maxResult = possResult;
        }
    }
}
System.out.println(maxResult);

At the end we print the maximum result which is: 906609

Checking if a number is a palindrome

This is a somewhat more complex piece of code and it works on a couple of assumptions.

The functions starts by declaring a variable named reverse to build the reversed number into. Then it enters a while loop which loops as long as the input argument variable named number is not 0.

The next line, the first in the loop multiplies reverse by 10, This adds a 0 at the end. Then add the remainder of number modulo by 10, Which is the last digit of number. Then we remove the last digit of the number which was just added to the reverse variable by dividing it by 10. This works because long does not work with a fractional part, only whole part.

public static long reverseNumber(long number){
    long reverse = 0;
    while(number != 0){
        reverse = reverse * 10;
        reverse = reverse + number % 10;
        number = number / 10;
    }
    return reverse;
}

With this we have all we need to reverse a whole number.

Check out the ‘Project Euler in Java’ page for more solutions!

Link to github.

That was Project Euler problem 4 in Java!