2
\$\begingroup\$

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.

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ You have an error in your logic: you are not always generating the highest available product. 995*999 is larger than 996*996, yet has not been considered. If both were palindromes, your code would return a large palindrome but not the largest. To guarantee you’ve found the largest palindrome, you would need to continue the outer loop until x*999 is less than the palindrome you found. Each inner loop can be abandoned once x*y is less the discovered palindrome. \$\endgroup\$
    – AJNeufeld
    Nov 28, 2018 at 15:24
  • \$\begingroup\$ Also, highestPalindrome is either undeclared or zero in your cout statement. You’d need to either output product or assign product to highestPalindrome. \$\endgroup\$
    – AJNeufeld
    Nov 28, 2018 at 15:33
  • \$\begingroup\$ next(x*y for x in range(30, 0, -1) for y in range(30, x-1, -1) if x*y == int(str(x*y)[::-1])) demonstrating the logic bug in "Performance improvement 3" for finding the largest palindrome for product of two integers between 1 & 30. It returns 676 for 26*26. Unfortunately, 696 (which is 24*29) is larger. \$\endgroup\$
    – AJNeufeld
    Nov 29, 2018 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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