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[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) + ")."
C++ Output

C++ Output

Advertisements