Stuck on problem 8 of project euler, getting wrong answer but the code seems right

Question

#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;

int main(){
    int arr[1000] = {0} ;
    int k = 0 ;
    string s ;
    for (int i=0 ; i<20 ; i++){
        cin >> s ;
        for (int j=0 ; j<50 ; j++){
            arr[k] = (int)(s[j]-'0') ;
            k++ ;
        }
    }
    long long int product = 1 , maxi = 0 ;
    for (int i=0 ; i+12 < 1000 ; i++){
        product = arr[i]*arr[i+1]*arr[i+2]*arr[i+3]*arr[i+4]*arr[i+5]*arr[i+6]*arr[i+7]*arr[i+8]*arr[i+9]*arr[i+10]*arr[i+11]*arr[i+12] ; 
        if (maxi < product){
            maxi = product ;
        }
    }
    cout << maxi << endl ;
    return 0 ;
}

The code seems fine to me and I am getting 2091059712 output all the time which the problem is rejecting. Please can you find out the anomaly

Please note that you don't need to perform *all* the multiplications every time. See e.g. [here](https://stackoverflow.com/questions/58075338/no-output-shown-on-problem-8-of-project-euler), even if it's a bit of a shameless plug, I'm afraid. — Bob__, Mar 25 '20 at 12:27

score 0 · Accepted Answer · answered Mar 25 '20 at 11:00

Your array elements are of type int, so multiplication of them is done using int -- even though the result is being assigned to a long long int, that doesn't affect the calculation. That causes an overflow because in the worst case the product of 13 digits can be as large as 13^9 = 2541865828329 which exceeds INT_MAX, which is probably 2^31 - 1. Perhaps using long long int for the array type, or cast the elements to a larger int type before multiplying them.

Thanks, It was quite helpful. – ANURAG BISHT Mar 25 '20 at 18:04 — ANURAG BISHT, Mar 25 '20 at 18:04

score 0 · Answer 2 · answered Mar 25 '20 at 11:50

The calculation of product in your code really should be done using a loop.

Instead of this:

product = arr[i]*arr[i+1]*arr[i+2]*arr[i+3]*arr[i+4]*arr[i+5]*arr[i+6]*arr[i+7]*arr[i+8]*arr[i+9]*arr[i+10]*arr[i+11]*arr[i+12] ;

try this:

for (product=arr[i], j=1; j<13; j++) product *= arr[i+j];

Not only is it much shorter and much easier to read, maintain and debug, but it will also avoid the integer overflow errors that were causing your program to give the wrong answers.

In C, an expression that multiplies two int variables (like arr[i]*arr[i+1]) will generate an int result. If this result is too large to fit inside an int variable (typically limited to 2³¹−1, which is much smaller than 9¹³), then it will overflow and you'll get the wrong result.

On the other hand, if you multiply a long long int variable by an int variable (as in product *= arr[i+j]), the int value will be promoted to long long int before the calculation is performed. This behaviour is called "type promotion". You can read more about it here.

Stuck on problem 8 of project euler, getting wrong answer but the code seems right

2 Answers2