Project Euler #8, I don't understand where I'm going wrong

Question

I'm working on project euler problem number eight, in which ive been supplied this ridiculously large number:

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

and am supposed to "Find the thirteen adjacent digits in the 1000-digit number that have the greatest product." EG the product of the first four adjacent digits is 7 * 3 * 1 * 6. My code is the following:

int main() {     string num = /* ridiculously large number omitted */;     int greatestProduct = 0;     int product;     for (int i=0; i < num.length() -12; i++)     {         product = ((int) num[i] - 48);         for (int j=i+1; j<i+13; j++)         {             product = product * ((int) num[j] - 48);             if (greatestProduct <= product)             {                 greatestProduct = product;             }         }     }     cout << greatestProduct << endl; } 

I keep getting 2091059712 as the answer which project euler informs me is wrong and I suspect its too large anyway. Any help would be appreciated.

EDIT: changed to unsigned long int and it worked. Thanks everyone!

Answer 1

In fact your solution is too small rather than too big. The answer is what was pointed out in the comments, that there is integer overflow, and the clue is in the fact that your solution is close to the largest possible value for an signed int: 2147483647. You need to use a different type to store the product.

Note that the answer below is still 'correct' in that your code does do this wrong, but it's not what is causing the wrong value. Try taking your (working) code to http://codereview.stackexchange.com if you would like the folks there to tell you what you could improve in your approach and your coding style.

Previous answer

You are checking for a new greatest product inside the inner loop instead of outside. This means that your maximum includes all strings of less or equal ton 13 digits, rather than only exactly 13.

This could make a difference if you are finding a string which has fewer than 13 digits which have a large product, but a 0 at either end. You shouldn't count this as the largest, but your code does. (I haven't checked if this does actually happen.)

for (int i=0; i < num.length() -12; i++) {     product = ((int) num[i] - 48);     for (int j=i+1; j<i+13; j++)     {         product = product * ((int) num[j] - 48);     }     if (greatestProduct <= product)     {         greatestProduct = product;     } }