Select Page

Project Euler 4 Problem 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

Project Euler 4We can quickly brute force a solution by searching both factors downwards from 999 as it is more likely to find a larger product from larger factors. We test each product as a palindrome and save it and continue until we exhaust all of our potential factors.

From the list of products we search for the maximum as our result.

Here’s my initial simple brute-force solution; about 0.3 seconds, but not fast enough for The HackerRank Version.

A simple brute force method
print max(i*j for i in xrange(100,1000) for j in xrange(i,1000) if str(i*j)==str(i*j)[::-1])

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 ≤ a ≤ 9, b ≤ 9, c ≤ 9

So, for our product to be a palindrome one of our factors has to be a multiple of 11. This allows us to decrease our search index, j, by 11 when i is divisible by 11. Otherwise, when i is not divisible by 11 we have to decrease j by 1.

The final solution is presented below and performs an exhaustive investigation of 3-digit factors starting from the biggest factors until a maximum palindrome product is found1. There’s an early out condition that breaks the inside loop (j) by finding a palindrome less than the current maximum. This is allowed because palindrome products are found in descending order from the perspective of the inside loop.

One subtle optimization was to check the limit before checking if the product is a palindrome as the palindrome check is more computationally expensive. If the first condition is false the succeeding conditions are ignored.

if p < L and is_palindromic(p): x, y, pmax = i, j, p

HackerRank version

HackerRank specifies a limit, 101101 < N < 1000000. No changes are required.

Python 2.7 Source

Last Word

The largest palindrome for some other cases (Note: I restricted the search range to something sane):

# 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
  1. There are only 279 6-digit palindromes which are products of two 3-digit numbers.