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

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 
#include 
#include 
bool isPalindrome(std::string num);
int findLargestProduct();
int main(){
        std::cout  largest){
                                largest = prod;
                        }
                }

        }
        return largest;
}

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

StackExchange Code Review Q#115482, answer score: 10