Dynamic Array C

Question

I am trying to solve the Dynamic Array problem of Hackerrank in C. I tried so many ways but all in vain. The best I could do is to clear 4 test cases. I am getting a segmentation error. Please help me find where am I doing wrong. It will be really helpful.

Question Link: https://www.hackerrank.com/challenges/dynamic-array/problem

We are supposed to complete the function. So here is my attempt:

int *dynamicArray(int n, int queries_rows, int queries_columns, int **queries, 
                  int *result_count) {
    *result_count = 0;
    int *result = (int *)malloc(queries_rows * sizeof(int));
    int i = 0, j = 0, y, x;
    int lastAnswer = 0;
    int **arr = (int **)malloc(n * sizeof(int *));
    int *size = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
        size[i] = 0;
    }
    for (i = 0; i < n; i++) {
        arr[i] = (int *)malloc(n * sizeof(int));
    }
    for (i = 0; i < queries_rows; i++) {
        x = queries[i][1];
        y = queries[i][2];
        if (queries[i][0] == 1) {
            size[(x ^ lastAnswer) % n]++;
            arr[(x ^ lastAnswer) % n][size[(x ^ lastAnswer) % n] - 1] = y;
        } else {
            lastAnswer = arr[(x ^ lastAnswer) % n][y % size[(x ^ lastAnswer) % n]];
            printf("%d\n", lastAnswer);
            (*result_count)++;
            result[(*result_count) - 1] = lastAnswer;
        }
    }
    result = (int *)realloc(result, (*result_count) * sizeof(int));

    return result;
}

Did run your code in a **debugger** to see where that error occurs, then run it again with a breakpoint near that failure so you can step carefully ahead and watch what happens leading up to that point? — tadman, May 10 '20 at 22:56
Actually, as of now I don't know debugging using a debugger. — Tushar Agrawal, May 11 '20 at 00:21
All the code provided at that link is naively written. Since they are apparently concerned with performance, those who made that site should read [Correctly allocating multi-dimensional arrays](https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays). — Lundin, May 11 '20 at 07:31
`queries` is supposed to be *string queries[q]: an array of query strings*. Are you sure about the function prototype? — chqrlie, Jan 14 '21 at 15:57
How do you know all the subarrays in `arr` will be at most `n` items? Could it be you need to reallocate them occasionally when appending values? — Dmitri, Jan 14 '21 at 16:21

chqrlie · Answer 1 · 2021-01-14T16:29:57.113

Your implementation is a little too complicated: you should use an intermediary variable idx as specified in the problem statement:

Create a 2-dimensional array arr, of n empty arrays. All arrays are zero indexed.
Create an integer lastAnswer, and initialize it to 0.
There are types of queries:
Query: 1 x y
Find the list within arr at index idx = (x ^ lastAnswer) % n.
Append the integer y to the arr[idx].
Query: 2 x y
Find the list within arr at index idx = (x ^ lastAnswer) % n.
Find the value of element y % size(arr[idx]) where size is the number of elements in arr[idx], Assign the value to lastAnswer.
Print the new value of lastAnswer on a new line.

Assuming the function prototype is correct, here is a simpler version:

int *dynamicArray(int n, int queries_rows, int queries_columns, int **queries, 
                  int *result_count) {
    int **arr = (int **)malloc(n * sizeof(int *));
    int *size = (int *)calloc(n * sizeof(int));
    int *result = (int *)malloc(queries_rows * sizeof(int));
    int i, j;
    int count = 0;
    int lastAnswer = 0;

    for (i = 0; i < n; i++) {
        arr[i] = (int *)malloc(n * sizeof(int));
    }
    for (i = 0; i < queries_rows; i++) {
        int x = queries[i][1];
        int y = queries[i][2];
        int idx = (x ^ lastAnswer) % n;
        if (queries[i][0] == 1) {
            arr[idx][size[idx]++] = y;
        } else {
            lastAnswer = arr[idx][y % size[idx]];
            printf("%d\n", lastAnswer);
            result[count++] = lastAnswer;
        }
    }
    *result_count = count;
    for (i = 0; i < n; i++) {
        free(arr[i]);
    }
    free(arr);
    free(size);    
    
    return (int *)realloc(result, count * sizeof(int));
}

The problem with this implementation is the size of the lists in the array arr may grow larger than n. You should therefore reallocate them as you append values.

Here is a modified version:

int *append_list(int **list, int size, int value) {
    *list = realloc(*list, (size + 1) * sizeof(int));
    (*list)[size] = value;
    return p;
}

int *dynamicArray(int n, int queries_rows, int queries_columns, int **queries, 
                  int *result_count) {
    int **arr = (int **)malloc(n * sizeof(int *));
    int *size = (int *)calloc(n * sizeof(int)); // initializes to 0
    int *result = NULL;
    int i, j;
    int count = 0;
    int lastAnswer = 0;

    for (i = 0; i < n; i++) {
        arr[i] = NULL;
    }
    for (i = 0; i < queries_rows; i++) {
        int x = queries[i][1];
        int y = queries[i][2];
        int idx = (x ^ lastAnswer) % n;
        if (queries[i][0] == 1) {
            append_list(&arr[idx], size[idx]++, y);
        } else {
            lastAnswer = arr[idx][y % size[idx]];
            printf("%d\n", lastAnswer);
            append_list(&result, count++, lastAnswer);
        }
    }
    for (i = 0; i < n; i++) {
        free(arr[i]);
    }
    free(arr);
    free(size);    
    
    *result_count = count;
    return result;
}

Dynamic Array C

1 Answers1