I'm having problems with Project Euler #8

Question

Here is my code for Project Euler #8. It reads the 1000-digit number from a file by reading each character, and then converting that to an integer before storing it into an array. I then intended on using loops to read groupings of 13 digits, 0-12, 1-13, 2-14, etc. And multiplying them. If the result is larger than the previous largest one, it is stored into num2.

#include <iostream>
#include <fstream>

using namespace std;

int num1=1, num2;

int main(){

    int digitArray[1000];
    char ctemp;
    int itemp;

    ifstream myfile;
    myfile.open("1000 digit number.txt");
    if(myfile.is_open()){
        for(int i=0; i < 1000; i++){
            myfile >> ctemp;
            itemp = ctemp - '0';
            digitArray[i] = itemp;
        }
    }
    myfile.close();

    for(int i = 0; i < 1000; i++){
        int j = i;
        while(j != (i+13)){
            num1 *= digitArray[j];
            j++;
            if(j == 1000){
                break;
            }
        }
        if(num1 > num2){
            num2 = num1;
        } else {}
    }

    cout << num2 << endl;

    return 0;

}

This code outputs the value 5000940, which is not the correct answer. Help?

Well, what is the number you input and what is the right answer? Why do you hardcode 1000 in the source instead of checking how long the input is? Then you could start testing your code with smaller inputs that are easier to verify. — Goswin von Brederlow, May 26 '22 at 16:05
Are you maybe supposed to use a sliding window approach? Multiply the first 13 digits and then use: `num1 = num1 / digitArray[i] * digitArray[i + 13];`. — Goswin von Brederlow, May 26 '22 at 16:09
The number is pulled directly from the one that Project Euler provides. It is 1000 digits long. I did verify that the program is pulling the number correctly by having it output the entire array. The issue lies in the multiplication somewhere. — colinkehoe, May 26 '22 at 16:30
Shameless plug: https://stackoverflow.com/a/58081796/4944425 . Please note the paragraph about the `int` type. — Bob__, May 26 '22 at 18:03
`num2` is not initialized, and `num1` needs to be initialized inside the outer loop and your break is too late, move that up. — Goswin von Brederlow, May 26 '22 at 18:56
@GoswinvonBrederlow Please note that, in the posted code, `num2` is a [global variable](https://stackoverflow.com/questions/2091499/why-are-global-and-static-variables-initialized-to-their-default-values). — Bob__, May 26 '22 at 19:03

Mohammad Rifat Arefin · Answer 1 · 2022-05-26T16:50:56.887

0

num1 is not initialized to 1 for every 13 contiguous numbers. Also check the break condition before any out of bound index is accessed.

 for(int i = 0; i < 1000; i++){
        int j = i;
        num1=1;
        while(j != (i+13)){
            if(j == 1000){
                break;
            }
            num1 *= digitArray[j];
            j++;
            
        }
        if(num1 > num2){
            num2 = num1;
        } 
    }

edited May 26 '22 at 16:50

answered May 26 '22 at 16:04

Mohammad Rifat Arefin

399
3
10

Avoid the `break` by limiting how high `i` can go. – Goswin von Brederlow May 26 '22 at 16:07
I'm confused. Its right there that I initialize num1 to 1. If you don't, it multiplies everything by zero and the output of the function will be zero. Since we're only using multiplication and not addition, using 1 is safe. – colinkehoe May 26 '22 at 16:31
@colinkehoe You do it only once. You need to do it every time you start multiplying 13 digits. If you had avoided using global variables the problem wouldn't have come up at all. – Goswin von Brederlow May 26 '22 at 16:49
Yeah, that's why I initialized it inside the for loop. @colinkehoe – Mohammad Rifat Arefin May 26 '22 at 16:49
I changed it so that num1 is initialized inside the for loop. Now the program is spitting out 2091059712 as an answer, which is also wrong. – colinkehoe May 26 '22 at 17:37

Goswin von Brederlow · Answer 2 · 2022-05-26T19:40:45.887

Streamlining the algorithm I came up with this:

#include <iostream>
#include <string>
#include <cstdint>

int main(){
    std::string input;
    // std::cin >> input;
    input = "1101111111111133111111111111122";
    uint64_t prod = 1;
    uint64_t m = 0;
    size_t count = 0;
    for (auto p = input.begin(); p != input.end(); ++p) {
        prod *= *p - '0';
        if (prod == 0) {
            prod = 1;
            count = 0;
        } else {
            if (count++ >= 13) {
                prod /= *(p - 13) - '0';
            }
            if ((count >= 13) && (prod > m)) m = prod;
        }
    }
    std::cout << "max = " << m << std::endl;
}

The approach uses a sliding window updating the product from digit to digit. It starts with a window size of 0 and grows it to 13 before doing that and every time a '0' is seen the window size is reset to grow again.

score 0 · Answer 3 · answered May 26 '22 at 19:54

Here is what worked:

#include <iostream>
#include <fstream>

using namespace std;

int main(){

    int digitArray[1000];
    char ctemp;
    int itemp;

    ifstream myfile;
    myfile.open("1000 digit number.txt");
    if(myfile.is_open()){
        for(int i=0; i < 1000; i++){
            myfile >> ctemp;
            itemp = ctemp - '0';
            digitArray[i] = itemp;
        }
    }
    myfile.close();

    long num2; 

    for(int i = 0; i < 1000; i++){
        int j = i;
        long num1 = 1;
        while(j != (i+13)){
            if(j == 1000){
                break;
            }
            num1 *= digitArray[j];
            j++;
        }
        cout << endl;
        if(num1 > num2){
            num2 = num1;
        } else {}
    }

    cout << num2 << endl;

    return 0;

}

Needed to make num2 a long, moved the break up, and initialized num1 inside of the for loop instead of outside. Honestly didn't expect to need a value that large. Embarrassing but whatever. Thanks for the help.

I'm having problems with Project Euler #8

3 Answers3