### 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