Project Euler #4 - Finding the largest palindrome that is the product of two three-digit numbers.

Question

This is my attempt at the 4th problem on Project Euler:

#include "stdafx.h"
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int palindromeCheck(int pp) {
    int temp = pp;
    string palindrome = std::to_string(pp);

    auto it1 = palindrome.begin();
    auto it2 = palindrome.end() - 1;

    while (it2 - it1 >= 1) {
        if (*it1 == *it2) {
            ++it1;
            --it2; 
        }
        else {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int highestPalindrome = 0; 
    for (int x = 100; x <= 999; x++) {
        for (int y = 100; y <= 999; y++) {
            int newDigit = x * y;
            int paliCheck = palindromeCheck(newDigit);
            if (paliCheck == 1) {
                if (newDigit > highestPalindrome) {
                    highestPalindrome = newDigit;
                }
            }
        }
    }
    std::cout << highestPalindrome; 
}

I'm trying to get better at both C++ and problem-solving so any help/tips are appreciated.

Answer 1

using namespace std; is a bad practice. You should should spell out either what you are using, or spell out explicitly the std:: when you are using something. You are doing the latter already with std::to_string and std::cout, just not with string.

Your palindromeCheck function should return a bool, instead of an int with specific integers having certain meanings.

temp is not used.

You are checking both 100 * 101 and 101 * 100. Multiplication is commutative, so you can cut your work in half by adjusting your inner y loop to only use number from a range which hasn't been checked yet (from x to 999, inclusive).

newDigit is an odd variable name for the product of x * y.

palindromeCheck(newDigit) is an expensive operation. newDigit > highestPalindrome is a relatively cheap test. Consider reversing the order of these tests to avoid calling an expensive function when the result will never be used.

Answer 2

Performance improvement

AJNeufeld's answer is correct that you don't need to test both 100*101 and 101*100, you're doing double work. The fix for that is small: don't evaluate any y that is smaller than x (or, in other words: start processing the inner loop when y == x and then increase the y value)

for (int x = 100; x <= 999; x++) {
    for (int y = x; y <= 999; y++) {

---

Performance improvement 2

For every iteration you do, it makes no sense to start checking from the lowest value, since you're only interested in the highest value.

Suppose you're in the inner loop, and for a given x value, you find a match for y=105 and also a match for y=305. Since the value of x remains unchanged, you can conclusively state that x*305 will always be bigger than x*105 and thus your initial match is meaningless, you only want the biggest match.

You can massively improve this by starting with the highest y and working your way down. For the sake of simplicity, I'm only changing the y iteration for now:

for (int x = 100; x <= 999; x++) {
    for (int y = 999; y >= x; y--) {

When you find your first matching y value (e.g. 305), then you know that you don't need to check any lower value for y anymore, as its product (with the same x value) will always be lower than the match you already found.

You can apply the same logic to the x iteration: start from the highest.

for (int x = 999; x >= 100; x--) {
    for (int y = 999; y >= x; y--) {

---

Performance improvement 3

Having this improved approach, there is a massive improvement we can make. First, let's look at which (x,y) values will be checked in the nested loops

  X  |  Y 
===========
 999 | 999
     |
 998 | 999
 998 | 998
     |
 997 | 999
 997 | 998
 997 | 997
     |
 996 | 999
 996 | 998
 996 | 997
 996 | 996

You can see that the order of operations always tests the highest available (so far untested) pair of numbers. That means that when you find a palindrome, that you already know that you have the highest available product since bigger numbers always make for a bigger product, and thus you also know that you have the biggest (possible) palindrome.

When that biggest possible palindrome is tested and turns out to actually be a palindrome, then you don't need to look for any other palindromes anymore as you know you've found the biggest possible one already.

for (int x = 999; x >= 100; x--) 
{
    for (int y = 999; y >= x; y--) 
    {
        int product = x * y;
        if(palindromeCheck(product))
        {
             std::cout << highestPalindrome; 
             return;
        }
    }
}
std::cout << "No palindrome found!?"; 
return;

Note: I used a return here to show that you can exit both loop at this point and there's no need to iterate any further. How you exit these loops can be done in many ways, but I tend to stick to methods that return as its maximizes both readability and ease of implementation.

---

Smaller comments

int palindromeCheck(int pp) {

Don't use unreadable parameter names. The amount of characters used in a parameter makes no different to the runtime of the application but it has a massive impact on readability. I assume pp stands for possiblePalindrome, so use the full name instead.

while (it2 - it1 >= 1) {

I would suggest using while (it1 < it2) as it's more readable (but exactly the same from a technical perspective)

int palindromeCheck(int pp) {
    // ...
        return 0;
    // ...
    return 1;
}

Don't use integer values for what is clearly intended to be a boolean value. Booleans exist for a reason, use them.

Methods should generally be phrased as imperative commands or questions. checkPalindrome would be better. But given this returns a boolean, isPalindrome would be even better.

This makes using the method a lot simpler and more readable: if(isPalindrome(12321))

int newDigit = x * y;

newDigit is a meaningless name that doesn't tell me anything about the value stored inside of it. product is much clearer since this variable contains the product of x and y.