Project Euler #4 - Largest Palindrome Product

Question

Problem Statement:

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.

This code is in C++ 11, please review my code.

#include <iostream>
#include <math.h>

using namespace std;

int palindrom(int num);

int main()
{
    auto n1 = 999u;
    auto n2 = 999u;
    unsigned int n = 0u;

    unsigned int largest = 0;

    for (; n1>=100; n2--)
    {
        if (n2 < 100)
        { 
            n1--; 
            n2 = 999; 
            continue; 
        }

        if (palindrom(n1*n2) == n1*n2)
        {
            cout << "n1 << " << n1 << " n2 " << n2 << endl;
            cout << n1*n2;

            if (largest < n1*n2)
                largest = n1*n2;
        }
    }

    cout << "Largest" << largest << endl;

    return 0;
}

int palindrom(int num)
{
    int new_num = 0;
    int digit = 0;

    while (num != 0)
    {
        digit = num % 10;
        new_num = new_num*10 + digit;
        num /= 10;
    }

    return new_num;
}

Output (project Euler solution kept secret)

906609

Answer 1

1. The way you've constructed your loop is awkward and hard to reason about.

   Why not just use a pair of nested loops?

   for(int i=100; i<1000; ++i) {
       for(int j=i; j<1000; ++j) {
           ...do stuff with (i,j)...
       }
   }
   

2. Don't use unsigned values unless you really need them.

3. I'd make palindrome() into a boolean predicate personally:

   bool is_palindrome(int n) { ... }
   

4. Don't recalculate the value of n1*n2 over and over again, assign it to a named variable and refer to that. It makes your code more readable & reduces the opportunity for errors to creep in.

Answer 2

Your function palindrom just "reverses" your number without actually checking it is a palindrom. It would probably be more appropriate to give this function a proper name like reverse_number() and to use it in a different function which can be called is_palindrome().

Please note that a faster implementation for this could be done differently as one could stop as soon as 2 digits do not match but we can consider that this is good enough: it's easy to test and it's easy to understand how it works.

Also, you could get rid of the magic number 10. You could for instance provide the base with a default argument.

You should always try to define your variable in the smallest possible scope.

Here's what I have for the helper function :

int reverse_number(int num, int base = 10)
{
    int new_num = 0;

    while (num != 0)
    {
        int digit = num % base;
        new_num = new_num*base + digit;
        num /= base;
    }
    return new_num;
}

bool is_palindrom(int num)
{
    return num == reverse_number(num);
}

---

You should compile your code with all warnings activated as they can provide you good hints :

euler3.cpp:28:18: warning: unused variable ‘n’ [-Wunused-variable]

---

The way you are iterating is super weird. If you want to iterate over a range with n1 and iterate over another range with n2, just use two nested for loops:

for (auto n1 = 999u; n1>=100; n1--)
for (auto n2 = 998u; n2>=100; n2--)

Also, without any loss of generality, one can assume that n1 >= n2 :

for (auto n1 = 999u; n1>=100; n1--)
for (auto n2 = n1;   n2>=100; n2--)

---

Because the values will get smaller, you can break when you find a value smaller that the one you have already found.

At the stage, my code looks like:

int main()
{
    unsigned int largest = 0;

    for (auto n1 = 999u; n1>=100; n1--)
    {
        for (auto n2 = n1;   n2>=100; n2--)
        {
            auto prod = n1*n2;
            if (prod < largest)
                break;

            if (is_palindrom(prod))
            {
                cout << "n1 << " << n1 << " n2 " << n2 << " -> " << prod << endl;
                largest = prod;
            }
        }
    }
    cout << "Largest" << largest << endl;
    return 0;
}

Answer 3

n is an unused variable. Your compiler should have warned you about it (and you should compile with warnings enabled).

Declaring variables with auto and an unsigned integer literal is unconventional. Just int n1 = 999 would have been more readable.

Your for-loop is weird. The three fields of a for-loop header should clearly state how the loop behaves. Testing for n1 >= 100 while decrementing n2, then having a separate test for n2 < 100 that decrements n1 and resets n2 is a really convoluted way of writing a nested for-loop!

Since n1 and n2 are symmetric, you can cut the work in half by making the inner loop condition n2 >= n1 instead of n2 >= 100.

palindrom() would be better named reverse() or reverse_digits().

Testing whether the product exceeds the largest palindrome so far is cheaper than testing whether the product is a palindrome, so do the cheaper test first.

#include <iostream>
// You don't need <math.h>

int reverse(int num)
{
    int new_num = 0;
    while (num != 0)
    {
        int digit = num % 10;     // Move the declaration inside the loop
        new_num = new_num * 10 + digit;
        num /= 10;
    }
    return new_num;
}

int main()
{
    int largest = 0;
    for (int n1 = 999; n1 >= 100; n1--)
    {
        for (int n2 = 999; n2 >= n1; n2--)
        {
            int product = n1 * n2;
            if (product > largest && reverse(product) == product)
            {
                largest = product;
            }
        }
    }
    std::cout << "Largest " << largest << std::endl;
    return 0;
}

Answer 4

You could use a while loop instead of this:

for(; n1>=100; n2--)

It would look cleaner like this:

while(n1 >= 100) {
    // ... some code here
    n2--;
}