Runtime error while adding printf statement

Question

Why it is giving runtime error while adding printf statement in the last? And just after the removing the printf statement, no error.

#include <stdio.h>

#define MOD 1000000007
#define MAX 44721

int main() {
    long long int test, i, j, store[1000009], n, m, x, a[1000006];
    scanf("%lld", &test);
    for (i = 0; i < 1000006; i++) {
        store[i] = 1LL;
    }
    a[0] = 1;

    for (j = 1; j < 1000006; j++) {
        for (i = 1; i < MAX; i++) {
            if (i % 2 == 0) {
                store[i] = (store[i - 1] + store[i]) % MOD;
            }
        }
        a[j] = store[MAX - 1];
    }
    printf("%lld", a[1]);
    return 0;
}

Answer 1

First of all you should pick a language as C is different from C++. As your code is C my solution will be in C too.

Running your code under Valgrind cleary shows that you are experiencing a stack overflow. The size of the arrays on the stack are too big.

Valgrind output:

==14228== Invalid write of size 4
==14228==    at 0x100000DC7: main (prova.c:6)
==14228==  Address 0x1038c062c is on thread 1's stack
==14228==  in frame #0, created by main (prova.c:6)

The size of the stack is system-dependent, the default on many system is 8MB, on unix/linux you can see it issuing the commnad ulimit -a. You may want to look at this post for more information about how stack and heap works.

The correct solution is to allocate arrays dynamically:

store = malloc(1000009 * sizeof(long long int));
if (store == NULL) {
  // The memory allocation failed, exit
  return(1);
}

a = malloc(1000006 * sizeof(long long int));
if (a == NULL) {
   return(1);
}

Remember to always check the return value of malloc ;)

Answer 2

There's 2 main problems here.

Your code is probably failing because of retrun 0; (fix: return 0;)

Second, you are allocating 2 really big array in the stacks, and you will, 99% of the times, end up getting stack overflow;

Note: long long int, is the same as long long:

You should consider using:

std::vector<long long> store(10000009);

or

std::unique_ptr<long long[]> store = std::make_unique<long long[]> (10000009);

or

   long long* store = new long long[10000009]

or

   auto* store = new long long[10000009]

or if you are using c... since you have both tags

   long long* store = (long long *)malloc(sizeof(long long) * 10000009);

or if you are using MSVC, you can use the __int64 keyword if what you want is a int of 64 bits [8 bytes])

std::vector<__int64> store(1345134123);

I normally prefer that over long long

And you could do a typedef long long __int64 if you end up using another compiler.

Answer 3

You allocate 2 large arrays of long long int in automatic storage, that's more than 8MB of stack space. You probably cause a stack overflow. It is possible that the compiler optimizes out most of your code if you remove the printf since none of it has any observable behavior without it.

In C, allocate the arrays with malloc:

#include <stdio.h>
#define MOD 1000000007
#define MAX 44721

int main(void) {
    long long int test, i, j, n, m, x;
    long long int *store = malloc(1000009 * sizeof(*store));
    long long int *a = malloc(1000006 * sizeof(*a));

    scanf("%lld", &test);
    for (i = 0; i < 1000006; i++) {
        store[i] = 1LL;
    }
    a[0] = 1;

    for (j = 1; j < 1000006; j++) {
         for (i = 1; i < MAX; i++) {
             if (i % 2 == 0) {
                 store[i] = (store[i - 1] + store[i]) % MOD;
             }
         }
         a[j] = store[MAX - 1];
    }
    printf("%lld", a[1]);
    return 0;
}