This is the fourth post in my Project Euler series. The third problem is here.
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is
.
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: . 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.
1 2 3 4 5 6 7 8 9 10 11 12 |
long reverseLong(long x) { long y = 0; int digit; while (x > 0) { digit = x % 10; y = (y * 10) + digit; x /=10; } return y; } |
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.
1 2 3 4 |
BOOL isPalindrome(long n) { return n == reverseLong(n); } |
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 then you never need to calculate
because multiplication is commutative. Because of this, we only need to calculate all values of
where
and x and y are both 3 digit numbers. If we were to calculate all values of
including those where
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.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
long foo() { long max = 0; for(int x = 100; x <= 999; x++) { for(int y = x; y <= 999; y++) { long product = x * y; if(product > max && isPalindrome(product)) { max = product; } } } return max; } |