Project Euler 8 in C++, I don't know what's wrong

Question

The problem from here: find nbAdjacent digits in nStr with highest product. So I stored the number as a string and everything my code prints is correct yet the final result is wrong, I can't figure out why... I've continued Project Euler in the meantime but this is bugging me. Here's my code:

std::string nStr = "731...50";  // a 1000-digit number
uint64_t prod = 1;
int nbAdjacent = 13;
int max = 0;
for (int i = 0; i <=988; i++)
{
    for (int j = 0; j < nbAdjacent; j++)
    {
        // yes i thought about that ;)
        prod *= nStr[i + j] - '0';
    }
    if (prod > max)
    {
        max = prod;
        for (int j = 0; j < nbAdjacent-1; j++)
            std::cout << nStr[i + j] << " * ";
        // each new max is printed
        std::cout << nStr[i + nbAdjacent - 1] << " = " << prod << std::endl;
    }
    prod = 1;
}

and it prints this:

7 * 3 * 1 * 6 * 7 * 1 * 7 * 6 * 5 * 3 * 1 * 3 * 3 = 5000940
4 * 9 * 1 * 9 * 2 * 2 * 5 * 1 * 1 * 9 * 6 * 7 * 4 = 9797760
9 * 2 * 2 * 5 * 1 * 1 * 9 * 6 * 7 * 4 * 4 * 2 * 6 = 13063680
2 * 5 * 1 * 1 * 9 * 6 * 7 * 4 * 4 * 2 * 6 * 5 * 7 = 25401600
5 * 1 * 1 * 9 * 6 * 7 * 4 * 4 * 2 * 6 * 5 * 7 * 4 = 50803200
1 * 1 * 9 * 6 * 7 * 4 * 4 * 2 * 6 * 5 * 7 * 4 * 7 = 71124480
1 * 9 * 6 * 7 * 4 * 4 * 2 * 6 * 5 * 7 * 4 * 7 * 4 = 284497920
9 * 6 * 7 * 4 * 4 * 2 * 6 * 5 * 7 * 4 * 7 * 4 * 2 = 568995840
5 * 3 * 4 * 9 * 1 * 9 * 4 * 9 * 3 * 4 * 9 * 6 * 9 = 1020366720
3 * 4 * 9 * 1 * 9 * 4 * 9 * 3 * 4 * 9 * 6 * 9 * 8 = 1632586752
9 * 1 * 9 * 4 * 9 * 3 * 4 * 9 * 6 * 9 * 8 * 3 * 5 = 2040733440
8 * 6 * 9 * 4 * 7 * 8 * 8 * 5 * 1 * 8 * 4 * 3 * 8 = 2972712960

I checked for index error in the for loops but found nothing wrong...

Answer 1

Here is my solution:

#include "stdafx.h"
#include <iostream>
#include <string>
std::string returnStr(std::string text, int index){
    std::string result = "";

    for (int i = index; i < text.size() && result.size() != 13; i++)
        result += text[i];
    if (result.size() == 13)
        return result;
    else
        return "";
}
long long int returnProduct(std::string str){
    int b = 0;
    long long int p = 1;
    for (int i = 0; i < str.size(); i++){
        b = str[i];
        b -= 48;
        p *= b;
    }
    return p;
}
int _tmain(int argc, _TCHAR* argv[])
{
    std::string text = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    long long int max = 0;
    for (int i = 0; i < text.size(); i++)
    {
        std::string s = returnStr(text, i);
        if (s != ""){
            long long int p = returnProduct(s);
            
            
            if (p>max)
                max = p;
        }

    }
    std::cout << max << std::endl;
    std::system("pause");
    return 0;
}

Answer 2

One problem in your solution is that you iterate up including 988, which is incorrect because you will access nStr[i + j] = nStr[988+12]=nStr[1000] which is out of bounds and contains garbage. As others pointed out, the max solution you could get is 9^13 which requires at least 42 bits (log2(9^13)=41.2), therefore use something like long long int that is guaranteed to have 64 bits on all architectures. As a tip, try to avoid hard-coding values such as 988 in your program but to compute them.

For the code, a possible improvement is to use a sliding window rather than computing the product each time, and to keep track of the current 13 digits multiplied. You then divide by the last digit and multiplying by the new one each loop iteration. This provides a speedup on the solution, that will be O(n) rather than O(s*n). Since some digits might be zero, we can keep a counter of how many digits are 0 in our window and if this counter is >0 we will know that the product is 0.

Here a sample solution in c++ that outputs the right result.

#include <iostream>
#include <string>

using namespace std;

const string digits = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
const int nAdj = 13;

int main()
{
    int n = digits.size();
    long long int prod = 1;
    long long int max = 0;
    int zeros = 0;

    // precompute sliding window
    for (int i = 0; i < nAdj-1; ++i)
    {
        int d = digits[i]-'0';
        if(d==0) ++zeros;
        else prod *= d;
    }

    for (int i = nAdj-1; i < n; ++i)
    {
        // add new digit
        int d = digits[i]-'0';
        if(d==0) ++zeros;
        else prod *= d;

        //check best
        if(zeros == 0)
        {
            if(prod > max) max = prod;
        }

        //remove last digit
        d = digits[i-nAdj+1]-'0';
        if(d==0) --zeros;
        else prod /= d;
    }

    cout << "The max is: " << max << endl; // 23514624000
    return 0;
}