Project Euler – Problem 4

This is the fourth post in my Project Euler series. The third problem is here.

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 \cdot 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I was a little disappointed at the simplicity of this problem. There’s just not really much to it. First off, we need to know how to determine if a number is a palindrome. To do this, we need to be able to calculate a number’s reverse. We can obtain the digits of a number 1 at a time by using the modulo operator. Example: 17 \mod 10 = 7. Knowing this, we simply need to remove a digit from x and put it onto y until there are no more digits on x (making sure to shift the digits on y as we go of course.

This is simple enough. As we know from the description of the problem, a palindrome is something that reads the same forward and backward. So from here it’s a pretty obvious step to know if a number is a palindrome.

From here, there’s nothing left but looping through to find the largest palindromic number. There’s not really much room for optimization, however I did find some. Assuming that you always calculate x \cdot y then you never need to calculate y \cdot x because multiplication is commutative. Because of this, we only need to calculate all values of x \cdot y where x > y and x and y are both 3 digit numbers. If we were to calculate all values of x \cdot y including those where x < y then we would perform roughly twice as many multiplications, something that really isn’t a big deal for such a small amount of math (but imagine if you had to solve this problem by hand.)

 

Leave a Reply

Your email address will not be published. Required fields are marked *