Largest Palindrome Product -

Premise

Before we continue, I would like to note that the solutions for the first 100 problems are free to be shared online according to the FAQ at Project Euler. But I don’t want just to give you the answer; I want to share the problem-solving process that I applied while working on these problems and the ‘aha’ moments. So if you prefer this instead of a code snippet – please keep on reading.

We are continuing with yet another Project Euler problem.

This one states:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is $9009=91\times99$ .

Find the largest palindrome made from the product of two 3-digit numbers.

Solution

Again, let us explain the concept of palindromic numbers:

A palindromic number is a number that remains the same when its digits are reversed. For example, 121, 1331, and 12321 are palindromic numbers because they read the same backward as forward.

So, the problem asks us to find the largest palindromic number made from the product of two 3-digit numbers.

The simplest way to solve this problem is to iterate through all possible products of two 3-digit numbers, checking whether the product numbers are palindromes. We’ll start from the largest product (999 * 999) and work our way downwards. A good optimization practice is the fact that once we find a number compare the next possible product and if it is smaller than our palindrome we can break the check, since we already found our largest palindrome. The time complexity of this solution is $O(n^2)$ , since we need to go through all the possible product combinations.

JavaScript

function findPalindrome() {
    let maxPalindrome = 0;
    
    for(let i = 999; i > 99; i--) {
        for(let j = i; j > 99; j--) {
            let product = i * j;
            if(product <= maxPalindrome) {
                break;
            }
            
            if(isPalindrome(product)) {
                maxPalindrome = product;
            }
        }
    }
    return maxPalindrome;
}

function isPalindrome(num) {
    return num == num.toString().split('').reverse().join('');
}

console.log(findPalindrome());

Python

def is_palindrome(n):
    return str(n) == str(n)[::-1]

def find_palindrome():
    max_palindrome = 0
    
    for i in range(999, 99, -1):
        for j in range(i, 99, -1):
            product = i * j
            if product <= max_palindrome:
                break
            if is_palindrome(product):
                max_palindrome = product
    return max_palindrome

print(find_palindrome())

Facebook Tweet Pin LinkedIn