Problem 4

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.

Note: It takes some trial, maths equation & observation to do it manually. You do the maths.

Solution 1: Brute Forcing

Let's iterate the variable a & b through all three digit numbers(100-999) and check if it is palindrome and largest.

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


largest = 0
for a in range(100, 1000): for b in range(100, 1000): if isPalindrome(a*b) and largest < a*b: largest = a*b

print(largest)

This code run: ~1.453120231628418.
The output: 906609

Now improving is so interesting. Did you see the redundancy! we checked when (a = 991 & b = 100) and (a = 100 & b = 991). C'mon multiplication is commutative. This will reduce the time by half.

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


largest = 0 for a in range(100, 1000):
# We reduce half of redundancy by starting from a for b in range(a, 1000): if isPalindrome(a*b) and largest < a*b: largest = a*b

print(largest)

This code run: ~0.7499971389770508. Reduced by half.
The output: 906609

Solution 2: Improved

Why just we start from greatest three digit number?

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


ans = 0
for a in range(999, 99, -1): for b in range(a, 99, -1): if isPalindrome(a*b): if ans < a*b: ans = a*b
break print(ans)

This code run: ~0.5156266689300537. Not much.
The output: 906609

You know when previous a is greater than a b must greater than previous b to be in the business. So let's make b greater than the previous b

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


ans = 0 low = 99
for a in range(999, 99, -1): for b in range(a, low, -1): if isPalindrome(a*b): if ans < a*b: ans = a*b
low = b # Min a and max b may exceed break # max a and min b.

print(ans)

This code run: ~0.015625476837158203. This is my best record.
The output: 906609