Problem 004 : Largest palindrome product

Largest palindrome product

Problem 4

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.

                                                                                                           https://projecteuler.net/problem=4

Problem 4 is about palindrome number.

The term "palindrome" is applicable for words, numbers, and any phrases.

(i.e. "race car" can be reversed to "rac ecar" which reads "race car")

(i.e. "1234321" can be reversed to "1234321" which is same as before)

(i.e. the longest palindromic phrase known starts with "a man, a plan, a cameo, .."

       and ends with "...., a canal, Panama!")

When we reverse number, we can manually divide each digit and recreate a reversed number, but that way will take a long time to compute and therefore inefficient.

Instead, we can convert number into string and reverse string using StringBuffer.

The source code is right here below:

public static boolean isPalin(String n)
{
    return (new StringBuffer(n).reverse().toString().equals(n));
}

We now need to think about finding the largest product.

Our approach will take from the largest 3-digit integers, since that way we can reduce execution time a lot. Starting with i = 999, we will automatically stop when the next i is less than square root of the largest product found so far, since smaller i from that point will never produce larger product.

In the nested for loop, we will stop the loop when the product is less than the product found. Because we are reducing the value of j, further calculation is unnecessary for it will produce smaller product.

int ans = 0;
for (int i = 999; i >= Math.sqrt(ans); i--)
{
    for (int j = i; j >= 100; j--)
    {
        int temp = i*j;
        if (temp < ans) break;
        else if (isPalin(String.valueOf(temp))) ans = temp;
    }
}

Answer is 906609
Execution time is 6 ms, or 0.006 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem004.java