Project Euler Problem 4 Solution

Project Euler Problem 4 Solution

The largest palindrome product

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 4 Statement

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.

Solution

Using a hammer

print (max(i*j for i in range(901, 1000, 2) for j in range(i, 1000, 2) if str(i*j)==str(i*j)[::-1]))
Xanax comic

We can quickly brute force a solution by checking all 3–digit factor pairs. We take advantage of the commutative property of multiplication to eliminate checking similar factors. For example, $997\times 909$ has the same product as $909\times 997$. This is the reason for the second loop starting at the last index of the first loop.

We also call upon the principal of the self–fulfilling prophecy. This means that we don’t know for sure that the largest palindrome will start with $9$, but if it did that would make for a much smaller search range. This would allow us to improve the search significantly by following two very important assumptions:

1. If the largest palindrome starts with $9$ then it would also end with a $9$, and we would need to only look at odd factors. Conveniently, only $1\times 9$, $9\times 1$, $7\times 7$, and $3\times 3$ result in the last digit being $9$ and making both factors odd. This allows us to increment the loop by two.

2. We only need to search from $901$ to $999$ since those are the only possible factors that would produce a product with a first digit of $9$.

If we run the program and it doesn’t produce an answer, then we would know our prophecy was not fulfilled and the largest palindrome does not start with $9$. This is trivial for two 3–digit factors, but becomes more challenging with seven or more–digit factors if further investigation is pursued.

This version runs instantly, about 1 millisecond, but not fast nor flexible enough for the HackerRank version.

Getting real with HackerRank

I'm going to concentrate on the HackerRank version because all this simple trickery doesn’t work when we are searching for any palindrome in a given search range, especially when several queries are made.

Now, we need to generate all palindromes from two 3–digit factors and save them to a list, sorted in ascending order.

A post here demonstrates how to speed things up significantly. It summarizes that if a six digit number is palindromic it must follow the form:

$$ 10^5 \cdot a + 10^4 \cdot b + 10^3 \cdot c + 100 \cdot c + 10 \cdot b + a\\ 100001a + 10010b + 1100c\\ 11(9091a + 910b + 100c) $$

Where $a$, $b$, and $c$ are integers such that $1\le a\le 9, b\le 9, c\le 9$

This means that one of our target factors has to be divisible by $11$ and allows us to increment our inside loop's search index, j, by $11$ when i is not divisible by $11$. Whenever i is divisible by $11$ we have to increment j by $1$.

The final solution is presented below and performs an exhaustive investigation of 3–digit factors and records each palindromic product into a dictionary. After the loops finish, the dictionary is converted to a list and sorted into descending order. This list can then accommodate multiple queries to find the largest palindrome within a search limit.

Here is a typical Python idiom for searching a sorted list for the closest value not meeting nor exceeding a target value, K.

q =  min(lst, key=lambda x:x>=K)

One subtle optimization was to check the minimum product, p, first, as the is_palindromic() function is computationally more expensive. This is because when the first logical and condition of an if statement is false then all following conditions are ignored.

if p >= 101101 and is_palindromic(p): dd[p]=1

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 4

HackerRank’s Project Euler Problem 4 runs 100 test cases and asks us to find the nearest palindrome product less than a limit, 101101 < K < 106

Python Source Code

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

dd = dict()
for i in range(101, 1000):
    for j in range(121, 1000, (1 if i%11==0 else 11)):
        p = i*j
        if p >= 101101 and is_palindromic(p): dd[p]=1
lst = sorted(list(dd), reverse=True)
K = int(input("Enter a number between 101101 and 999999? "))
q =  min(lst, key=lambda x:x>=K)
print ("the nearest palindrome less than", K, "is", q)

Last Word