CODEWITHSUNDEEP
c++stringalgorithm
tedled
tedled

Reputation: 21

Finding Palindromes from the product of two numbers with N digits

My code compiles but seems as if it may never find the answer. This is odd since I have looked at code that is almost identical that finishes in seconds.

Here is my code:

#include <iostream>

#include <sstream>

int main()
{
       for(int i = 999; i >=100; i--)
       {
              for(int j=999; j>=100;j--)
              {
                     int num = (i*j);
                     std::string number;
                     std::string temp;
                     std::string reversed;
                     std::stringstream out;
                     out << num;
                     number = out.str();
                     temp = number;
                     std::reverse(temp.begin(),temp.end());
                     if( temp == number)
                     {
                           std::cout << number << std::endl;
                     }

              }
       }



       std::cin.get();
       return 0;
}

Now here is code that I know works and works incredibly fast. I don't see what we are doing differently.

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    // Count down from largest to smallest, so first palindrome found is the largest

    unsigned biggestProduct = 0;

    for(unsigned n1=999; n1>=100; --n1) {
        for(unsigned n2=999; n2>=100; --n2) {
            unsigned thisProduct = n1 * n2;

            if(thisProduct > biggestProduct) {
                stringstream strmProduct;
                string strProductReverse;

                strmProduct << n1 * n2;

                strProductReverse = strmProduct.str();
                reverse(strProductReverse.begin(), strProductReverse.end());

                if(strmProduct.str() == strProductReverse)
                    biggestProduct = thisProduct;
            }
        }
    }

    cout << biggestProduct << endl;
    cin.get();

    return 0;

}

Upvotes: 0

Views: 947

Answers (5)

SoFar67
SoFar67

Reputation: 3

Here are couple issues I can point to:

  • This line of code: for(int j=999; j>=100;j--) can be reduced to for(int j=999; j>=i-1;j--).This is to avoid running through number twice. example: for i=999 you will go through j counter, starting with 999, followed by 998, 997, etc. It would save time if you skip everything lower or equal to 998 since i=<998 and j=999 would make those combinations
  • The second hint is in the question: you are looking for the largest, meaning that the first palindrome is the largest. So you need to filter whatever combination you have beyond that. You have it in the second code by adding if(thisProduct > biggestProduct).

  • Also steps for the counter can be crucial. From this discussion I found that changing the step size to 2 could be useful.

  • Last but not least is strings. I learnt here also that making strings could be computationally expensive. Editing the block with std::string could be another option.

Upvotes: 0

MSN
MSN

Reputation: 54634

The difference between the two is that the first tests for palindromeness for every i*j, while the other only tests i*j greater than the biggest palindrome its already found.

It can be made slightly faster by going from j= i to j>=100 and earlying out when i*j<= biggestProduct or when i*i<= biggestProduct.

Upvotes: 1

Karoly Horvath
Karoly Horvath

Reputation: 96286

The biggest difference is this line if(thisProduct > biggestProduct). If the product is smaller than the current biggest you don't have to check whether is palindrome.

Upvotes: 3

john
john

Reputation: 87997

OK, assuming a correction to the for loops, there's an important difference in the two pieces of code. The second faster piece of code only attempts to find the largest palindrome, so it avoids a lot of work. Your code attempts to find all palindromes which is obviously a harder problem and is going to take more time.

Upvotes: 1

zw324
zw324

Reputation: 27220

for(int i = 999; i <=100; i--)

Will this ever run (same for j)? :)

for(int i = 999; i >=100; i--)

Upvotes: 4

Related Questions