Help with program for solving Project Euler Problem #8

The program I wrote below seems to be doing its job, but it produces the wrong answer. As described in the comments, I need to multiply 5 consecutive digits of the 1000-digit string and then find the largest product throughout the entire string.

/*
OBJECTIVE: Multiply five consecutive numbers and then compare products to find largest product
PROVE: 40824
*/

#include <iostream>

using namespace std;

int main()
{
    // string length is 1000 characters
    string str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    int store = 0; // what I need to compare total to later
    int total = 1; // total must be '1' for multiplication or result is always '0'

    for(int i = 0;i<=999;) // i = 0 because that's the starting point for place of first number in string (str[0]); because the length is 1 short, 999 is the limit
    {
        total = 1; // what will be multiplied by inputs from str[]
        int incr = i + 4; // places for the nex开发者_JAVA百科t 5 now that 0-4 are out of the way would be 5,6,7,8,9

        // A general note: pattern this generates is that the end digit of an even break in groupings will always either be 4 or 9
        // e.g. breaking the loop at position 44, 199, 234 will multiply 5 places properly without error

        if(i == 0) // when starting out i = 0
        {
            for(;i<=4;i++) // i = str[0] which is then incrmemented to str[4] which is fifth number
            {
                cout << "i: " << i << '\t' << "str[" << i << "]: " << str[i] << '\t';
                total*=(str[i] - '0'); // takes str[1],str[2],...str[4] and multiplies them together using total as valueholder.
                // " - '0' " is because string numbers return ASCII codes
                cout << "Total Product: " << total << '\t';
                cout << "Store: " << store << '\t' << endl;
            };

            store = total > store ? total:store; // if total is greater than store, then store = total; simple enough
            cout << endl; // line-break after first set of five
        };

        if(i>=5) // i is no longer 0
        {
            for(;i<=incr;i++) // i must be added by 5 now because 0,1,2,3,4 are first five and 5,6,7,8,9 are next
            {
                cout << "i: " << i << '\t' << "str[" << i << "]: " << str[i] << '\t';
                total*=(str[i] - '0'); // takes str[1],str[2],...str[4] and multiplies them together using total as valueholder.
                // " - '0' " is because string numbers return ASCII codes
                cout << "Total Product: " << total << '\t';
                cout << "Store: " << store << '\t' << endl;
            };

            store = total > store ? total:store; // if total is greater than store, then store = total; simple enough
            cout << endl; // line-break after each set of five
        };
    };

    cout << endl << endl <<  store; // final output; what should be answer

    return 0;
}

The program shows that it is indeed multiplying five consecutive digits together and successfully bumping the store value when necessary, alas I still get a wrong answer of 31752 which should be 40824 (According to the Project Euler Solutions google-group: http://code.google.com/p/projecteuler-solutions/). What have I done wrong? What must I do to fix this program? Any tips for the future to avoid the probably-stupid mistake I'm not seeing?

---

From a cursory glance, I believe your problem lies in the fact that you modify i in multiple locations aside from the for loop declaration. This would cause your scan through the number to skip over sequences that could have potentially been correct.\

If you reason out your code, it starts at position 0 in the string. Then you have a conditional where you increment i 4 times, so then the next time through the loop, you start attempting to find a sequence starting at position 4 in the string, rather than starting at position 1.

---

Fixed Code:

/*
OBJECTIVE: Multiply five consecutive numbers and then compare products to find largest product
PROVE: 40824
*/

#include <iostream>

using namespace std;

int main()
{
    // string length is 1000 characters
    string str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
    int store = 0; // what I need to compare total to later
    int total = 1; // what will be multiplied by inputs from str[]
    int n = 0; // keeps track of single iterations

    for(int i = 0;n<=999;n++) // i = 0 because that's the starting point for place of first number in string (str[0]); because the length is 1 shorter, 999 is the limit
    {
        total = 1; // must be set back to one each successful product loop
        int incr = n + 4; // places for the next 5 after 0

        // A general note: pattern this generates is that the end digit of an even break in groupings will always either be 4 or 9
        // e.g. breaking the loop at position 44, 199, 234 will multiply 5 places properly without error

        if(n == 0) // string starts at 0, must be accounted for especially
        {
            for(;i<=4;i++) // i = str[0] which is then incrmemented to str[4] which is fifth number
            {
                cout << "n: " << n << '\t' << "str[" << i << "]: " << str[i] << '\t';
                total*=(str[i] - '0'); // takes str[1],str[2],...str[4] and multiplies them together using total as valueholder.
                // " - '0' " is because string numbers return ASCII codes
                cout << "Total Product: " << total << '\t';
                cout << "Store: " << store << '\t' << endl;
            };

            store = total > store ? total:store; // if total is greater than store, then store = total; simple enough
        };

        for(;i<=incr;i++) // i must be added by 4 now because 0,1,2,3,4 are first five and 1,2,3,4,5 are next
        {
            cout << "n: " << n << '\t' << "str[" << i << "]: " << str[i] << '\t';
            total*=(str[i] - '0'); // takes str[1],str[2],...str[4] and multiplies them together using total as valueholder.
            // " - '0' " is because string numbers return ASCII codes
            cout << "Total Product: " << total << '\t';
            cout << "Store: " << store << '\t' << endl;
        };

        store = total > store ? total:store; // if total is greater than store, then store = total; simple enough
        i = (n + 1); // i needs to start at a consecutive n each successful loop
    };

    cout << endl << endl <<  store;

    return 0;
}

---

well, this problem makes me think of the Pattern Match Algorithm "KMP". probably you should check out KMP, may gain some hint.