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:
- a nested for loop that finds products of all 3-digit factor pairs
- a function that converts a product into a string
- 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[0] == x[1]) {return true;} return false;} if (x[0] == 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[0] is x[1]): return True else: return False if (x[0] 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) + ")."