50169. Sum of Integers

I'm a slow walker, but I never walk backwards.

Task Description

We will compute the sum of integers pointed by blocks in a pointer array. The blocks are separated by NULL pointers within this array. As a result every block has at least one non-NULL pointer. Two consecutive NULL pointers indicate the end of the array. To simplify the task we assume that there will be at least one block. Please refer to the following figure.

figurefigure

Now we want to compute the sum of integers pointed by each block without duplication. A duplication is defined as having more than one pointers pointing to the same memory address within the same block. For example, in the figure above the second and the third pointers form a duplication. As a result the sum of the first block is 2 + 3 = 5, since the 3 will be summed only once due to duplication. Note that the duplication only happens within the same block. As a result the sum of the second block is -5 + 3 + 2 = 0. That is, the 2 will still be summed (but only once) even when it has been pointed by a pointer in the first block.

Note that we can check if a pointer has appeared within the same block by comparing it with every pointer before it, until we either hit a NULL or the beginning of the pointer array, as suggested by the following animation.

animationanimation

The prototype of the function sumOfIntegers is given by sumOfIntegers.h as follows.

void sumOfIntegers(const int *ptrArray[], int answer[], int *numberOfBlocks);

You need to write the sum of each block into answer and set *$numberOfBlocks$ to be the total number of blocks.

You can use the following main function to test your function:

Main Function 1

#include <stdio.h>
#include <stdlib.h>
#include "sumOfIntegers.h"
 
int main(int argc, char const *argv[])
{
    int a, b, c, d, number = 0;
    int *numberOfBlocks = &number;
    const int *ptrArray[16];
    int answer[16] = {0};
    scanf("%d%d%d%d", &a, &b, &c, &d);
    ptrArray[0] = &b;
    ptrArray[1] = &a;
    ptrArray[2] = &a;
    ptrArray[3] = NULL;
    ptrArray[4] = &d;
    ptrArray[5] = &a;
    ptrArray[6] = &b;
    ptrArray[7] = &b;
    ptrArray[8] = NULL;
    ptrArray[9] = &c;
    ptrArray[10] = NULL;
    ptrArray[11] = NULL;
    sumOfIntegers(ptrArray, answer, numberOfBlocks);
    for(int index = 0; index < *numberOfBlocks; index++) {
        printf("%d ", answer[index]);
    }
    return 0;
}

Main Function 2

#include <stdio.h>
#include <stdlib.h>
#include "sumOfIntegers.h"
 
int main(int argc, char const *argv[])
{
    int a, b, c, d, e, f, g, h, number = 0;
    int *numberOfBlocks = &number;
    const int *ptrArray[32];
    int answer[32] = {0};
    scanf("%d%d%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f, &g, &h);
    ptrArray[0] = &b;
    ptrArray[1] = &a;
    ptrArray[2] = &a;
    ptrArray[3] = &b;
    ptrArray[4] = &c;
    ptrArray[5] = &f;
    ptrArray[6] = &e;
    ptrArray[7] = &a;
    ptrArray[8] = &b;
    ptrArray[9] = &b;
    ptrArray[10] = NULL;
    ptrArray[11] = &d;
    ptrArray[12] = &g;
    ptrArray[13] = &e;
    ptrArray[14] = &b;
    ptrArray[15] = &f;
    ptrArray[16] = &c;
    ptrArray[17] = &f;
    ptrArray[18] = &c;
    ptrArray[19] = &a;
    ptrArray[20] = &a;
    ptrArray[21] = &e;
    ptrArray[22] = &d;
    ptrArray[23] = NULL;
    ptrArray[24] = &a;
    ptrArray[25] = &c;
    ptrArray[26] = &g;
    ptrArray[27] = &c;
    ptrArray[28] = &c;
    ptrArray[29] = &e;
    ptrArray[30] = NULL;
    ptrArray[31] = NULL;
    sumOfIntegers(ptrArray, answer, numberOfBlocks);
    for(int index = 0; index < *numberOfBlocks; index++) {
        printf("%d ", answer[index]);
    }
    return 0;
}

Main Function 3

#include <stdio.h>
#include <stdlib.h>
#include "sumOfIntegers.h"
 
int main(int argc, char const *argv[])
{
    int a, b, c, d, e, f, g, h, number = 0;
    int *numberOfBlocks = &number;
    const int *ptrArray[32];
    int answer[32] = {0};
    scanf("%d%d%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f, &g, &h);
    ptrArray[0] = &b;
    ptrArray[1] = NULL;
    ptrArray[2] = &c;
    ptrArray[3] = &e;
    ptrArray[4] = &a;
    ptrArray[5] = &b;
    ptrArray[6] = &a;
    ptrArray[7] = &c;
    ptrArray[8] = &c;
    ptrArray[9] = &g;
    ptrArray[10] = &c;
    ptrArray[11] = &b;
    ptrArray[12] = &g;
    ptrArray[13] = &e;
    ptrArray[14] = &a;
    ptrArray[15] = &f;
    ptrArray[16] = &g;
    ptrArray[17] = &b;
    ptrArray[18] = &a;
    ptrArray[19] = &a;
    ptrArray[20] = NULL;
    ptrArray[21] = &d;
    ptrArray[22] = NULL;
    ptrArray[23] = &c;
    ptrArray[24] = &g;
    ptrArray[25] = &e;
    ptrArray[26] = &d;
    ptrArray[27] = NULL;
    ptrArray[28] = &c;
    ptrArray[29] = NULL;
    ptrArray[30] = NULL;
    sumOfIntegers(ptrArray, answer, numberOfBlocks);
    for(int index = 0; index < *numberOfBlocks; index++) {
        printf("%d ", answer[index]);
    }
    return 0;
}

Input Format(for the test main.c)

The input has four integers. The pointers in the blocks will point to these integers.

Output Format(for the test main.c)

For each block, print the sum of the integers pointed by the block.

Subtasks

  • 10 points: There is only one block in $ptrArray$.
  • 90 points: There are multiple blocks in $ptrArray$.

Sample Input 1 (for the test main function 1)

3 2 2 -5

Sample Output 1 (for the test main function 1)

5 0 2

Sample Input 2 (for the test main function 2)

-12 -11 -2 13 -15 -9 -11 -15

Sample Output 2 (for the test main function 2)

-49 -47 -40

Sample Input 3 (for the test main function 3)

-8 10 0 -2 4 -8 -2 -2

Sample Output 3 (for the test main function 3)

10 -4 -2 0 0

Compile

gcc -std=c99 -O2 -c main.c
gcc -std=c99 -O2 -c sumOfIntegers.c
gcc -std=c99 -O2 sumOfIntegers.o main.o

Discussion