Project Euler: Problem 4
Largest Palindrome Product
Problem:
Find the largest palindrome made from the product of two 3-digit numbers.
Approach:
I broke this problem into 3 smaller sub-problems.
The first is taking an integer and breaking it into its digits. I wrestled with this for a little while but ended up with an elegant function using integer division.
The second is to determine if a number is a palindrome. Once I used the first function to break the number apart, it was fairly straight-forward to compare first and last digits, moving towards the center, and determining if they were the same number (ie a palindrome).
The third is to run through a set of two three-digit numbers and evaluate whether the product is a palindrome.
Challenges:
The first two problems were fairly straight-forward, although I did find increasingly more efficient ways to implement both functions, settling on two functions I will likely use again in the future. I’m not sure if they are optimal, but they seem to be the best I could come up with.
The third problem was interesting. I took a brute force approach at first, but that results in effectively all numbers between 100 and 999 multiplying together, or ~900² numbers. That takes a long time.
Getting smart about it, the largest result is very unlikely to be in any set other than 900+ multiplied by 900+, or written differently (>900,>900). Or possibly (>800, >900).
Also because i*j = j*i, no need to iterate through numbers I’ve already checked.
Implementing these two parts I ended up running from 900 to 999 for both numbers, with j always being larger than i. This results in a very fast execution.
Solution:
Next Steps:
This is still a bit of a guess-and-check solution, which is fine, but I feel that if the numbers were much larger, say 6-digit or 10-digit numbers, this would start to come crumbling down. There is likely a more efficient way of determining whether two numbers are going to be a palindrome product, but I couldn’t think of it at the time.
