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.