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

As above, we can quickly brute force a solution by checking all 3–digit factor pairs. We take advantage of the commutative property of multiplication to reduce redundant checks. For example, $997\times 909$ has the same product as $909\times 997$, so the second loop starts from the current 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 observations:

1. Odd Factors Only: If the palindrome starts and ends with 9, the product must result from odd factors. Thus, we can increment the loop by two.

2. Search Range: We only need to consider factors between 901 and 999, as these are the only three-digit numbers that can produce a product beginning with 9.

If this assumption fails (i.e., the largest palindrome does not starts with 9), we will extend the search, which is trivial for three-digit factors but more complex for larger factor sets.

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 "Going further with Project Euler 4" 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 solution performs a comprehensive exploration of all possible products of three-digit numbers to identify palindromic products. Each palindromic product is stored in a list. Once all iterations are complete, the list is sorted in descending order based on the product values. This approach ensures that the results are readily available for multiple queries, allowing quick retrieval of the largest palindrome within any specified search limit.

Here is a Python idiom for searching a descending sorted list for the biggest value not meeting nor exceeding a target value, K. So, for example, K=13; lst=[120,14,13,12,9,7,5,4,3,2,1] the result would be 12.

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:= i * j) >= 101101 and is_palindromic(p)

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 4

HackerRank 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

s_palindromic = lambda n: str(n)==str(n)[::-1]

dd = sorted([i * j for i in range(101, 1000) 
             for j in range(121, 1000, (1 if i % 11 == 0 else 11)) 
             if (p:= i * j) >= 101101 and is_palindromic(p)],
    reverse=True)

for _ in range(int(input())):
    K = int(input())
    q = min(dd, key=lambda x:x>=K)
    print(q)

Last Word