Home > Blockchain >  I'm having problems with Project Euler #8
I'm having problems with Project Euler #8

Time:05-27

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?

CodePudding user response:

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;
        } 
    }

CodePudding user response:

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.

CodePudding user response:

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.

  • Related