# Project Euler #4 - Largest Palindrome Product

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

• Note this meta post concerning this question: Keeping 'Competitive Results' private Mar 25 '14 at 22:53
• @rolfl Thanks for posting. Next time I will not add output in question. Secondly, I think Project Euler sort of sites are for self improvement, and you can harm yourself if you are cheating. Mar 26 '14 at 2:23

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.

• Note that (d) is really about reducing the opportunity for errors to creep into your code. It's better to assign n1*n2 to a suitably named variable & use that everywhere that you need it. That way you know you've used the same value everywhere and make the code more readable at the same time. Mar 25 '14 at 10:26
• Can you please elaborate, (c). Are you taking about overloading () operator Mar 25 '14 at 10:28
• A function named palindrome() sounds like it should return true if it is a palindrome and false if it isn't. A function named reverse() has no such connotation. If you keep the name palindrome(), then make it test for whether the parameter is a palindrome. Mar 25 '14 at 10:30
• "b) Don't use unsigned values unless you really need them." I disagree strongly. Signed integers may overflow with undefined behavior, but unsigned integers don't, which is a plus. Second, the range of unsigned integers is twice as large, hence it may be necessary to use int64_t instead of int32_t, but uint32_t may be sufficient. Yes, one has to be careful with unsigned integers (preventing unintentional overflow), but it's definitively not strictly worse than signed integers. Mar 25 '14 at 12:51
• @FrerichRaabe Well yes, but I guess you already got what I meant to say: the size of the positive range (and in this problem we only want positive numbers) is roughly twice as large for unsigned counterparts. Mar 25 '14 at 13:58

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;
}

• Wouldn't it be better to have a variable for n2 limit (n2>=n2_limit) and set it to n2 when we find a palindrom? Mar 25 '14 at 14:23
• It could probably do the trick but I am not quite sure I see the benefit compared to my solution. Mar 25 '14 at 14:34
• I like the break in the inner loop. If you change the inner loop limits so that n2 goes from 999 down to n1, you would probably find the largest palindrome sooner and make the break even more effective. Mar 26 '14 at 19:49

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;
}

• +1. One query why. int digit = num % 10; in loop, why shoul I not declare variable only once? Mar 25 '14 at 10:21
• Declaring the variable inside a loop does not make it any less efficient. It just makes it more tightly scoped so that it is only accessible from inside the loop. That makes it easier to maintain the code. Mar 25 '14 at 10:22

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--;
}