🔒 Problem

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.

🔐 Key Idea

🔑 Solution

🧭 Initial idea

$O(n^2)$ complexity, brute force method.

ans = 0

n = 999
m = 999

while n > 99:
    while m > 99:
        if str(n * m) == str(n * m)[::-1]:  # check whether the string equals the reversed string
            if n * m > ans:
                ans = n * m  # find the maximum palindromic number
        m -= 1
    n -= 1
    m = 999

print(ans)

906609

Note: Would’ve been a cleaner code with for i in range(100, 999): ....

Note: Could’ve reduced the number of iteration to half by setting m = n at the end of while statement. It will skip doing redundant calculations such as 999 * 998 and 998 * 999.

🎲 Difference of 80 method (from harveyramer in solution thread)

User harveyramer discovered the pattern that the two factor that makes the largest palindrome doesn't differ more than 80 numbers in the range.

🔐 Key idea

finding the pattern of the answer and reducing useless iterations

max = 0
k = 1000
last = 8 * k // 100 + 1  # 80 + 1 when k = 1000

for i in reversed(range(k - last, k)):  # 999, 998, 997, ...
    for j in reversed(range(i + 1 - last, i + 1)):  # i, i - 1, ... i - 80
        n = i * j
        if str(n) == str(n)[::-1]:
            if n > max:
                max = n

print(max)

906609