for C programmers

general
, , ,
1

Here are two codes one uses 2d array and other uses pointers.

The catch is the code with pointers runs fine and the other with 2d array gives segmentation fault in some test cases(not all). It passes all testcases n<=1000 .

Limit of n is 1< n <10000.

The logic of both code are correct.

Problem:

I need to know why the use of 2d array is giving segmentation fault. Is it bad to use 2d array and use pointers instead. But both are same things.

This is the code which gives segmentation fault

int main()
{
 
    /* Enter your code here. Read input from STDIn. Print output to STDOUT */
    int n, q, o, x, y, ti, pi, la, j;
 
    scanf("%d%d",&n,&q);
    int v[n][n],a[n];
 
    for (j = 0; j<n; j++)
        a[j] = 0;
 
    la=0;
    while(q-->0)
    {
        scanf("%d%d%d",&o,&x,&y);
        ti=((x^la)%n);
        switch(o)
        {
        case 1:
            v[ti][a[ti]]=y;
            a[ti]++;
            break;
 
        case 2:
            pi = y % a[ti];
            printf("%d\n", v[ti][pi]);
            la = v[ti][pi];
 
            break;
        }
    }
    return 0;
}

This code run fine

int main()
{
    int n, q, o, x, y, ti, pi, la;
    int *a, *s;
    int **v;
    scanf("%d %d", &n, &q);
    v = (int **)malloc(n * sizeof(int *));
    a = (int *)malloc(n * sizeof(int));
    s = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
    {
        s[i] = 1;
        v[i] = (int *)malloc(s[i] * sizeof(int));
        a[i] = 0;
    }
    la = 0;
    for (int i = 0; i < q; i++)
    {
        scanf("%d %d %d", &o, &x, &y);
        ti = (x ^ la) % n;
        if (o == 1)
        {
            v[ti][a[ti]] = y;
            a[ti] ++;
            if (a[ti] == s[ti])
            {
                 s[ti] *= 2;
                v[ti] = realloc(v[ti], s[ti] * sizeof(int));
            }
        }
        else
        {
            pi = y % a[ti];
            printf("%d\n", v[ti][pi]);
            la = v[ti][pi];
        }
    }
    free(s);
    free(a);
    free(v);
    return 0;
}

view full testcase here

http://www.writeurl.com/text/z2qlksiktbd7aeuvy3zj/dvgaqxcmeugthbkutrtn

2

You cannot create 2-D arrays of such big size. If N={10}^{5} , then you need {10}^{10} cells in memory which is ~1GB. Clearly exceeds the memory limit, hence runtime error/WA.

3

You are getting segmentation fault , because for large values of n , say n = 10^5 , it is directly trying to allocate a space of 10^5 * 10^5 * sizeof(int) bytes for the variable v .

While allocating memory for a 2-d array , the C compiler tries to allocate contiguous (i.e , adjacent) locations , i.e , it is looking for a huge empty space in the memory where it will keep all the integers side-by-side . At most cases this will give a segmentation fault as such a large single chunk of memory might not be available.

However , in the one with pointers , it is allocating only 10^5 * sizeof(int) bytes for v , and allocating each sub-pointer separately. Thus , it is not looking for a single huge chunk of memory , and can save the different pointers in different locations as it finds suitable. This is why it works.

I guess the lesson here is that when working with 2-d arrays in c , it is safer to work with pointers and not direct arrays . I hope I was of help :slight_smile:

2 Likes