September 6, 2011

Largest palindrome made from the product of two 3-digit numbers

This question is an entry level puzzle from Project Euler.

It is very interesting because it has far more pitfalls than it first appears to be. There are some helpful discussions to pick up the whole scenario of this puzzle: 1) and 2). Basically speaking, the first post listed the most straightforward thoughts, which is iterations two numbers both from 100 to 1000 and finding the maximum of the outcomes. While I wrote the algorithm, this is also the first idea came into mind while I added several optimizations on it.
1) Decrease one number 1 per step, and iterate the other one from 999 to 100.
2) Stop the step whenever it finds a palindrome and march to the next step by decrease the benchmark number by one.
3) Meanwhile, increase the lower bound of iterator from 100 to whenever it finds a palindrome. This will exponentially decrease the searching range. e.g. (A--benchmark number, B--iterator) if A*B==palindrome, the searching range for the next step would be [A-1, B]. Because if both numbers less than the previous finding, it must not be the LARGEST palindrome we would like to find.
4) The second stop criteria is the iterator equal or less than the lower bound mentioned in the last item.

The major pitfall that I did see quite a few people mentioned is alternative decrease two numbers from 999, which the result comes to be 834*836=698896. The difference for two numbers are obviously unnecessary to be less or equal to one.

The second reference provides the basic optimization from math point of view. All of the palindrome can be divided by 11, so...
P=100000x+10000y+1000z+100z+10y+x
P=100001x+10010y+1100z
P=11*(9091x+910y+100z)
Then, the question is simplified to find two 3-digit numbers, at least one of which should be divided by 11. Similarly as the previous method, if A can be divided by 11, decreasing B by one per time; and if A cannot divided by 11, decreasing B by 11 per time.

My solutions for the first 5 puzzles are here.
cheers,

No comments:

Post a Comment

Days of our lives

Daisypath Anniversary tickers