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.
First palindrome problem, yeah.
1) brute-force like usual:
Double loop from 100 to 999, check every product if is palindrome, return the largest.
2) Optimization:
Cut down the iterations by half by limiting the second integer no smaller than the first(since 123*999 == 999* 123), and reverse the looping order from 999 to 100 downwards.
3) Further optimization:
Assume the palindrome product is 6-digit, which is very likely. Then we parametrization the number:
P=100000x+10000y+1000z+100z+10y+x
P=100001x+10010y+1100z
P=11(9091x+910y+100z)
This indicate that if a*b=P, then at least one of a or b is divisible by 11. Thus we can step the second loop integer by 11 instead of 1 if the first loop integer is not a multiple of 11.
P.S. There seem to be no better approach to check a decimal palindrome other than simply reverse the number.
4) Alternative approach:
This problem can also be solved reversely, namely generate a possible palindrome first then check if the palindrome is a product of two 3-digit integers. Though it could be much slower in the worst case (the palindrome in search is a small 5-digit number).
- 999*999 = 998001 => largest palindrome possible = 997799
100*100 = 10000 => smallest palindrome possible = 10001
Thus we must split the solution into 6-digit and 5-digit cases.
- 6-digit: build the palindrome with a integer from 997 to 100 with concatenating its reverse.
5-digit: build the palindrome with a integer from 999 to 100 with concatenating its first 2 digits reverse.
- Check each palindrome number P with a factor from 999 to square root of P: P is the target number if P is divisible by the factor, and 99< P/factor <=100 (this is only necessary for 5-digit case actually).
P.S.2. This alternative approach had significantly outperformed the original method in my test environment by more than 2 times faster for this specific problem.
[GitHub Link] [Official overview pdf by projecteuler.net]
1) brute-force like usual:
Double loop from 100 to 999, check every product if is palindrome, return the largest.
2) Optimization:
Cut down the iterations by half by limiting the second integer no smaller than the first(since 123*999 == 999* 123), and reverse the looping order from 999 to 100 downwards.
3) Further optimization:
Assume the palindrome product is 6-digit, which is very likely. Then we parametrization the number:
P=100000x+10000y+1000z+100z+10y+x
P=100001x+10010y+1100z
P=11(9091x+910y+100z)
This indicate that if a*b=P, then at least one of a or b is divisible by 11. Thus we can step the second loop integer by 11 instead of 1 if the first loop integer is not a multiple of 11.
P.S. There seem to be no better approach to check a decimal palindrome other than simply reverse the number.
4) Alternative approach:
This problem can also be solved reversely, namely generate a possible palindrome first then check if the palindrome is a product of two 3-digit integers. Though it could be much slower in the worst case (the palindrome in search is a small 5-digit number).
- 999*999 = 998001 => largest palindrome possible = 997799
100*100 = 10000 => smallest palindrome possible = 10001
Thus we must split the solution into 6-digit and 5-digit cases.
- 6-digit: build the palindrome with a integer from 997 to 100 with concatenating its reverse.
5-digit: build the palindrome with a integer from 999 to 100 with concatenating its first 2 digits reverse.
- Check each palindrome number P with a factor from 999 to square root of P: P is the target number if P is divisible by the factor, and 99< P/factor <=100 (this is only necessary for 5-digit case actually).
P.S.2. This alternative approach had significantly outperformed the original method in my test environment by more than 2 times faster for this specific problem.
[GitHub Link] [Official overview pdf by projecteuler.net]