CODEWITHSUNDEEP
c++iterationlargenumber
steve john
steve john

Reputation: 41

Project Euler #8 Answer is to large to get valid answer

I have looked through the results on here to try to see where my error is. I am not looking for an answer to the solution but rather a hint as to what I overlooked to result in the wrong answer. That being said let's get into it.

I am working on Project Euler questions and I am currently on number 8. This question I believe is supposed to test you on your knowledge of iterating and storing large numbers. I have tried to store the value as an unsigned int, long long int, and as a string but all of which gave me different wrong answers. As I mentioned before, I was wondering if anyone could point me in the right direction to were I have overlooked or maybe have not researched thoroughly enough.

My code:

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
int main()
{
   vector<int> numberList = "I broke the number provided into individual one digit integers";
   string sum;
   string answer;

for(auto it = numberList.begin(); it != numberList.end(); it++)
    {
        auto it2 = next(it, 1);
        auto it3 = next(it2, 1);
        auto it4 = next(it3, 1);
        auto it5 = next(it4, 1);
        auto it6 = next(it5, 1);
        auto it7 = next(it6, 1);
        auto it8 = next(it7, 1);
        auto it9 = next(it8, 1);
        auto it10 = next(it9, 1);
        auto it11 = next(it10, 1);
        auto it12 = next(it11, 1);
        auto it13 = next(it12, 1);

        if(it12 == numberList.end())
        {
            break;
        }

        sum = to_string(*it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13);

        if(sum.compare(answer) > 0)
        {
            answer = sum;
        }
    }
    cout << answer << endl;
}

My plan of attack for this solution was to have 13 iterators that are updated on each loop and I would use these values to multiple and find the solution. The problem that I found was that the resulting number is to large for an int resulting on overflow. I then tried long long and unsigned which both resulted in a wrong answer. This version of the solution I tried to store it in a string which also resulted in a wrong answer. It is important to note that I am trying to keep this solution in linear time. Thanks for the help.

Upvotes: 0

Views: 56

Answers (1)

Holt
Holt

Reputation: 37616

On a standard architecture (where long long are 64 bits long), you should not need a std::string for this problem since you are multiplying 13 digits, so the result will always be less than 10^13, which easily fits in a long long (2^63 ~ 10^19).

The issue with your code is that you are performing the multipliation using int, so you overflow before the conversion:

sum = to_string(*it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13);

Here *it, *it2, ..., are iterators of int, so you get a product in the int domain which overflow before the conversion to_string.

You should use a std::vector<long long> to store the digits or converts the first one to a long long:

sum = (long long) *it * *it2 * *it3 * *it4 * *it5 * *it6 * *it7 * *it8 * *it9 * *it10 * *it11 * *it12 * *it13;

And sum / answer can simply be long long.

Upvotes: 4

Related Questions