Project Euler 8 in C, working with 4 digits and fails for 13 digits?

Question

I have coded the problem in C. When I run the code to find the solution for the four adjacent digits in the 1000-digit number that have the greatest product I get the correct answer. But with the 13 adjacent digits I am always getting the wrong answer (2039787520), can someone point it out where I am wrong?

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

//Storing the 1000 digits
char number_array[] =   "73167176531330624919225119674426574742355349194934"
                        "96983520312774506326239578318016984801869478851843"
                        "85861560789112949495459501737958331952853208805511"
                        "12540698747158523863050715693290963295227443043557"
                        "66896648950445244523161731856403098711121722383113"
                        "62229893423380308135336276614282806444486645238749"
                        "30358907296290491560440772390713810515859307960866"
                        "70172427121883998797908792274921901699720888093776"
                        "65727333001053367881220235421809751254540594752243"
                        "52584907711670556013604839586446706324415722155397"
                        "53697817977846174064955149290862569321978468622482"
                        "83972241375657056057490261407972968652414535100474"
                        "82166370484403199890008895243450658541227588666881"
                        "16427171479924442928230863465674813919123162824586"
                        "17866458359124566529476545682848912883142607690042"
                        "24219022671055626321111109370544217506941658960408"
                        "07198403850962455444362981230987879927244284909188"
                        "84580156166097919133875499200524063689912560717606"
                        "05886116467109405077541002256983155200055935729725"
                        "71636269561882670428252483600823257530420752963450";

int main(void){
  int length = sizeof(number_array);
  int64_t max_product = 0;
  int i, j;

   for( i = 0; i <= length - 13; i++){

     int64_t  product = 1;

      //Going through 13 consecutive digits for each digit in the char 
       array
      for(j = 0; j < 13; j++){
        printf("product -- > %d and number -- > %d\n",product ,
        (number_array[i+j] - 0x30));

        // finding the product
        product = product * (number_array[i + j] - 0x30);

      //if product is zero skipping the process
        if(product == 0){break;}
      }

     printf("product -- > %I64d\n", product);

     //checking for the max product
     if(product > max_product){
       max_product = product;
     }

   }

  printf("max_product -- > %I64d\n", max_product);
}

`

do not use magic numbers like 0x30 or 48. Use `'0'` instead. That describes the intention clearly and is more correct because the codepoint for `0` is not 48 in all character sets — phuclv, Apr 17 '17 at 06:18
and there are already a lot of questions about project Euler 8 like http://stackoverflow.com/q/8681642/995714, http://stackoverflow.com/q/20710051/995714 — phuclv, Apr 17 '17 at 06:19
The code invokes undefined behaviour for passing wrong parameter types to `printf` varargs. You seem to be aware about the wrong types, but your format strings are completely wrong. Use `inttypes.h` macros and correct them. — too honest for this site, Apr 17 '17 at 06:54
It's hard to know where you error in logic lies given the dearth of information you have provided. Your logic shows you read `987` of `1000` with your `i` loop (indexes `0` - `986`) and then for each element in your `j` loop you read `13`. (indexes `987` - `999`). You provided no way we can know if that is anywhere near right. It may be, it may not, but we have no way to know either way... — David C. Rankin, Apr 17 '17 at 07:47
`sizeof number_array` includes the null terminator in the size — M.M, Apr 17 '17 at 08:07

score 2 · Answer 1 · edited May 23 '17 at 12:17

2

I replaced int64_t type with long long and printed the value using the %lld format specifier with no other changes to your program and it works. The answer is correct.
For demo click here.

Be warned though. The answer to the Project Euler question 8 is there in the link as well. If you want to enjoy finding the answer yourselves, you better not scroll down too much in the page whose link is above.

Edit: As a comment made me realize after a bit of searching, long long is guaranteed to be at least 64 bits (as explained in here) but needn't be 64 bits. (ie, Could be more but not less).

If the long long won't do, you can use the unsigned version of int64_t which is uint64_t. This is guaranteed to be 64 bits. Nothing more. Nothing less. Like this:

uint64_t max_product;
printf("%" PRIu64 "\n", max_product);

Click here for the demo with uint64_t.

edited May 23 '17 at 12:17

Community

1
1

answered Apr 17 '17 at 06:41

J...S

5,079
1
20
35

`long long` is not guaranteed to have more than 64 bits. And for almost all current PC/server implementations it has not. – too honest for this site Apr 17 '17 at 06:52
@Olaf Gee, I didn't know `long long` wasn't 64 bits on most systems. In fact, I thought the exact opposite. All I've ever worked with is gcc. Thanks for correcting me. – J...S Apr 17 '17 at 07:13
You should read my comment carefully again. It did not say it has not 64 bits! And I definitively did not say it is guaranteed to have only 32 bits asthat's plain wrong, don't put words in my mouth. Please read the standard if you doubt me. `int64_t` is - otoh - guaranteed to have exactly 64 bits like `uint64_t`. That's the idea about the fixed width types. – too honest for this site Apr 17 '17 at 07:15
@Olaf When you say there is no __guarantee__ for `long long` to be 64 bits, did you mean it could be? Meaning many systems are probably having `long long` of size 64b but we can't rely on them being so? – J...S Apr 17 '17 at 07:20
2

last try: I never said "there is no guarantee for long long **to be** 64 bits"! **Please** read my comment once more! Precision is a vital part of programming! And read about the standard integer types! – too honest for this site Apr 17 '17 at 07:22
1

@J...S use the Ctrl+K / `{}` button to indent a code block. – Antti Haapala -- Слава Україні Apr 17 '17 at 08:05

Project Euler 8 in C, working with 4 digits and fails for 13 digits?

1 Answers1