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.
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]))
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×909 has the same product as 909×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×9, 9×1, 7×7, and 3×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:
Where a, b, and c are integers such that 1 ≤ a ≤ 9, b ≤ 9, c ≤ 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,
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’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)
- using a dict vs. a list has a slight improvement in speed
- There are only 279 6–digit palindromes which are products of two 3-digit numbers.
- The largest palindrome for some other cases:
# Digits factor 1 factor 2 product 4 9999 9901 99000099 5 99979 99681 9966006699 6 999999 999001 999000000999 7 9997647 9998017 99956644665999 8 99999999 99990001 9999000000009999 9 999920317 999980347 999900665566009999 10 9999986701 9999996699 99999834000043899999 11 99999943851 99999996349 9999994020000204999999 12 999999000001 999999999999 999999000000000000999999 13 9999996340851 9999999993349 99999963342000024336999999