Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
    
Note this meta post concerning this question: Keeping 'Competitive Results' private –  rolfl Mar 25 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. –  pranitkothari Mar 26 at 2:23

3 Answers 3

up vote 5 down vote accepted
  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.

share|improve this answer
    
+1. Really good advice. Thanks. –  pranitkothari Mar 25 at 10:22
    
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. –  Phil Armstrong Mar 25 at 10:26
    
Can you please elaborate, (c). Are you taking about overloading () operator –  pranitkothari Mar 25 at 10:28
1  
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. –  200_success Mar 25 at 10:30
3  
"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. –  stefan Mar 25 at 12:51

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;
}
share|improve this answer
    
+1. For magic number, scope of variable, and observing weird thing I did. –  pranitkothari Mar 25 at 10:37
    
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? –  Jakub Kania Mar 25 at 14:23
    
It could probably do the trick but I am not quite sure I see the benefit compared to my solution. –  Josay Mar 25 at 14:34
1  
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. –  200_success Mar 26 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;
}
share|improve this answer
    
+1. One query why. int digit = num % 10; in loop, why shoul I not declare variable only once? –  pranitkothari Mar 25 at 10:21
1  
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. –  200_success Mar 25 at 10:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.