Tags

Project Euler #4 finds the largest palindrome that is the sum of two 3-digit numbers:

`A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.`

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

My solution uses 3 chunks of code:

1. a nested for loop that finds products of all 3-digit factor pairs
2. a function that converts a product into a string
3. a function that determines if a string is a palindrome

As usual, I wrote the solution in C++ first, but this is really the first Project Euler problem that may have been easier in Python. It certainly is easier to read in Python – the language’s string syntax is much more straightforward than C++. The solutions are functionally identical, but I think the `isPalindrome()` code in Python is really much more readable.

Here it is in C++:

```#include <iostream>
#include <string>

using namespace std;

// the function isPalindrome returns true if a given string is a palindrome
bool isPalindrome(string x){
if (x.length() == 1){return true;}
if (x.length() == 2){if (x == x) {return true;} return false;}
if (x == x[x.length()-1]){return isPalindrome(x.substr(1,x.length()-2));}
return false;
}

// the function isPalindromeHelper converts an int into a string
// and returns the result of isPalindrome(<string>)
bool isPalindromeHelper(int x){
string numString = to_string(x);
return isPalindrome(numString);
}

int main()
{
int highestPalindrome = 0;
int highesti = 0;
int highestj = 0;
for (int i = 999; i > 99; i--){
for (int j = 999; j > 99; j--){
if (isPalindromeHelper(i*j)){
if (highestPalindrome < i*j){highestPalindrome=i*j; highesti=i; highestj=j;}
}
}
}
cout << endl << "The largest palindrome that is the product of two 3-digit numbers is: " << highestPalindrome << " (" << highesti << " x " << highestj << ")." << endl;
return 0;
}
```

And in Python:

```def isPalindrome(x):
if (len(x) is 1): return True
if (len(x) is 2):
if (x is x): return True
else: return False
if (x is x[-1]): return isPalindrome(x[1:-1])

def isPalindromeHelper(x):
numString = str(x)
return isPalindrome(numString)

highestPalindrome = 0
highesti = 0
highestj = 0
for i in range(100, 1000, 1):
for j in range(100, 1000, 1):
temp = i*j
if isPalindromeHelper(temp):
if (temp > highestPalindrome):
highestPalindrome = temp
highesti = i
highestj = j
print ""
print "The largest palindrome that is the product of two 3-digit numbers is " + str(highestPalindrome) + " (" + str(highesti) + "x" + str(highestj) + ")."```