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 [latex]9009 = 91 \cdot 99[/latex].
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: [latex]17 \mod 10 = 7[/latex]. 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 [latex]x \cdot y[/latex] then you never need to calculate [latex]y \cdot x[/latex] because multiplication is commutative. Because of this, we only need to calculate all values of [latex]x \cdot y[/latex] where [latex]x > y[/latex] and x and y are both 3 digit numbers. If we were to calculate all values of [latex]x \cdot y[/latex] including those where [latex]x < y[/latex] 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; } |