Project Euler #4 in C++: largest palindrome product of two 3-digit numbers

Question

Project Euler #4

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.

Any reviews are accepted.

#include <iostream>
#include <algorithm>
#include <string>
bool isPalindrome(std::string num);
int findLargestProduct();
int main(){
 std::cout << findLargestProduct() << std::endl;
 return 0;
}
bool isPalindrome(std::string num){
 std::string oldnum = num;
 reverse(oldnum.begin(),oldnum.end());
 if(oldnum == num)
 return true;
 else
 return false;
}
int findLargestProduct(){
 int largest,prod =0;
 for(int i =100;i<=999;i++){
 for(int j =100; j<=999;j++){
 prod = i*j;
 if(isPalindrome(std::to_string(prod)) && prod > largest){
 largest = prod;
 }
 }
 }
 return largest;
}

• SirPython: Welcome to Code Review! Good job on your first question.

Answer 1

Excessive spacing and main()

To start with, 4-space tabs please. 8 is tooooo much, you're using up all the horizontal space!

Additionally, return 0; from main() is optional. If you omit it, the compiler will provide it for you - so you don't have to write it.

isPalindrome()

This function doesn't modify its input - you take a copy, reverse it, and then compare the two. But actually you're making two copies of the input - one into num and the other into oldnum. If you took the argument by reference-to-const, you save yourself a copy for free:

bool isPalindrome(std::string const& num) { .. }

Additionally, the argument should probably be named oldnum - since that's the one that doesn't change.

Avoid code that looks like: if (expr) return true; else return false; That's an extremely verbose way of writing return expr; Altogether, this becomes:

bool isPalindrome(std::string const& oldnum) {
 std::string revnum = oldnum;
 std::reverse(revnum.begin(), revnum.end());
 return oldnum == revnum;
}

However, this is pretty inefficient - we have to make another copy of oldnum just to check if it's reversible? We can do that directly in one go. Just compare the ith element to the N-ith element and make sure they all line up:

bool isPalindrome(std::string const& num) {
 for (size_t i = 0; i < num.size()/2; ++i) {
 if (num[i] != num[num.size()-i-1]) {
 return false;
 }
 }
 // still here? must be a palindrome
 return true;
}

This saves you a copy, so will be quite a bit faster.

findLargestProduct()

There is undefined behavior here. When you write:

int largest, prod = 0;

That isn't initializing largest, only prod. Which is unfortunate since it's only largest that needs to be initialized. Avoid this kind of multiple initialization, and simply do:

int largest = 0;

prod you can simply declare inside the inner-most loop.

Now, the slowest part of this function is isPalindrome(). That's an expensive operation to do - so we want to do it as rarely as possible! As an optimization, we can check if prod > largest first - so you avoid the expensive logic in all the cases where the outcome doesn't matter. If the product isn't the new max, who cares, right? That is:

int prod = i*j;
if (prod > largest && isPalindrome(std::to_string(prod))) {
 largest = prod;
}

Once we're there, let's really make sure we never have to do it by iterating in the opposite order:

for (int i=999; i>=100; --i) {
 for (int j=999; j>=100; --j) {
 ...
 }
}

Math is cool

Assuming the answer will be 6 digits (seems safe), we know it's divisible by 11. We know this because the digits of the number will be \$abccba\,ドル and the handy rule for checking divisibility by 11 is to sum the even digits and the odd digits and check if the difference is divisible by 11 - and both the even digits (\$b+c+a\$) and the odd digits (\$a+c+b\$) have the same sum. Since we know it's divisible by 11, we know one of the factors must be divisible by 11. Let's pick j. This let's us reduce the loop to:

for (int i=999; i>=100; --i) {
 for (int j=990; j>=100; j-=11) { // largest 3-digit multiple of 11
 ...
 }
}

Breakdown of timing

Here's a breakdown of all the things I just suggested:

as-is 171.5ms
better isPalindrome 138.0ms
flip ordering 9.9ms
iterate backwards 4.8ms
count by 11s 0.2ms

Answer 2

I would suggest changing isPalindrome to accept an int parameter. That you determine if a number is a palindrome by formatting as a string is an implementation detail that callers don't need to know about. That leaves you the flexibility to change the implementation if you want. Extracting digits with things like (num / 10) % 10 may not be faster by itself, but you will avoid the string allocation.

• Juho: In my experience, extracting digits like this is generally much faster than playing around with strings. If you need speed, avoid strings and manipulate integers directly.

Answer 3

 for(int i =100;i<=999;i++){
 for(int j =100; j<=999;j++){
 prod = i*j;
 if(isPalindrome(std::to_string(prod)) && prod > largest){

As @Barry noted, you can save time by doing this in the opposite order. Another optimization is to stop looking once largest > prod. With this code, you could write that

 for (int i = 999; i >= 100; --i){
 for (int j = 990; j >= 100; j -= 11) {
 int product = i*j;
 if (largest >= product) {
 break;
 }
 if (isPalindrome(std::to_string(product))) {

Now it stops iterating through the inner loop once product is smaller than largest. This shaved off 10-20% of the time in my tests.

I changed from prod to product for readability reasons.

You can also break inside the isPalindrome if. For a given i, we'll never find a larger product, as the rest of the j values are smaller than the current one.