Storing and processing large arrays to compute dot products

Problem Statement (from HackerRank)


We have two arrays \$a\$ and \$b\$ of length \$N\$, initially all values equals to
zero. We have \$Q\$ operations. Let's define three types of operations on
this arrays:

• 1 l r c: Increase \$a_l, a_{l+1}, \ldots, a_r\$ by \$c\$.

• 2 l r c: Increase \$b_l, b_{l+1}, \ldots, b_r\$ by \$c\$.

• 3 l r: Print \$a_l\cdot b_l + a_{l+1}\cdot b_{l+1} +\ldots+ a_r\cdot b_r\$ in modulo \$1000000007\$.

Input Format


First line of the input consists of \$N\$ and \$Q\$. Next \$Q\$ lines contain one of the three types of operations.


Constraints

• \$1 \le N \le 10^9\$

• \$1 \le Q \le 200000\$

• \$1 \le c \le 10000\$

• \$1 \le l \le r \le N\$

Output Format


Whenever you get a type 3 operation, you should print the answer in a
new line.


Sample Input 1

5 3 
1 1 5 5 
2 2 4 2 
3 3 4

Sample Output 1

20

Sample Input 2

10 20
1 9 9 6768
2 5 5 2202
3 7 7
2 3 9 1167
2 1 7 8465
3 1 5
2 1 1 1860
3 9 9
2 5 5 2153
1 5 7 749
3 1 1
2 8 10 3129
3 1 1
1 2 10 2712
2 1 8 79
1 1 6 4645
1 7 7 1358
3 2 10
1 9 9 8677
3 8 10

Sample Output 2

0
0
7898256
0
0
506356461
98353320

How can I efficiently store and process data for this problem?

```
#include
#include
int main()
{
long n,q,ch,l,r,c,i,j;
/* n, q, l, r, c works as per problem statement.
ch is used to scan the first digit of operation.
i and j are used to control the loops. */
scanf("%ld %ld",&n,&q);
long a[n],b[n];
memset(&a, 0, sizeof a);
memset(&b, 0, sizeof b);
for(i=0;i<n;i++) //Init to 0
{
a[i]=0;
b[i]=0;
}
for(i=0;i<q;i++)
{
scanf("%ld ",&ch); //Look for the first digit
switch(ch)
{
case 1:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(j=l;j<r;j++)
a[j]+=c; //Adds c to every element of a

This is a fairly straightforward implementation that seems to get the job done at least for the simple input you posted. Overall, it's easy to read and understand, given the problem description. Here are some ways I think it could be improved.

Naming

You've named all the variables similarly to how they are named in the problem statement. That's fine for an assignment or exercise, but it would be a real pain to maintain later on. You have a comment describing the names, but it assumes the person reading it has the problem statement. That's rarely the case in the real world.

The variable names n, i, and j aren't terrible. I'd leave i and j, but rename n to something descriptive like numElements (or, if you prefer num_elements).

The names q, l, ch, r, and c are terrible and confusing. I'd make q something like numLines or numInputLines or something like that. l and r are the start and end of the range of indexes you want to modify, so I'd name them start and end.

c and ch are likely to be confused. Also, ch seems like it's a remnant from an earlier version when it was declared as a char type instead of a long. It's used to get the user's input, so you could name it userInput or mode or something more appropriate. c is the value you're adding to all the inputs. Since this is an exercise, it's just an abstract value that doesn't have any real meaning. Normally, I'd suggest calling it whatever it is, but that's hard in this case. Something generic like value or operand could work.

Functions

Your code does a few different things:

• Gets the size of the arrays and number of lines of input

• Creates and initializes the arrays

• Processes the inputs

You should separate those into functions like this:

#include 
#include 
#include 

int getNumberOfElementsAndLines (size_t* outElements, size_t* outLines)
{
    long numScanned = scanf("%zu %zu", outElements, outLines);
    int result = (numScanned == 2);
    if ((*outElements  1000000000) || (*outLines  200000))
    {
        result = 0;
    }

    return result;
}

int allocateAndInitArrays (const size_t numElements, long** outA, long** outB)
{
    // Make sure the inputs are valid
    if ((outA == NULL) || (outB == NULL) || (numElements == 0))
    {
        return 0;
    }

    // Allocate and clear A and if successful, allocate and clear B
    *outA = calloc (numElements, sizeof(**outA));
    *outB = calloc(numElements, sizeof(**outB));

    if (*outB == NULL)
    {
        free(*outA);
        *outA = NULL;
    }

    return ((*outA != NULL) && (*outB != NULL));
}

int getAndProcessInput (long* a, long* b, const size_t numElements, const size_t numLines)
{
    for (size_t i = 0; i < numLines; i++)
    {
        long mode   = 0;
        int numScanned = scanf("%ld ", &mode);
        if (numScanned != 1)
        {
            return 0;
        }

        long l, r, c;
        switch (mode)
        {
            case 1:
                scanf("%ld %ld %ld",&l,&r,&c);
                l--;
                for(long j = l; j < r; j++)
                    a[ j ] += c;    //Adds c to every element of a
                break;

            case 2:
                scanf("%ld %ld %ld",&l,&r,&c);
                l--;
                for(long j = l; j < r; j++)
                    b[ j ] += c;    //Adds c to every element of b
                break;

            case 3:
                scanf("%ld %ld",&l,&r);
                l--;
                c=0;
                for(long j = l; j < r; j++)
                    c += a[ j ] * b[ j ];   //Adds the product
                printf("%ld\n",c%1000000007);   //Prints the value after using mod
                break;

            default:
                // Error in input
                return 0;
                break;
        }
    }

    return 1;
}

Then your main would look something like this:

int main()
{
    int     result  = 0;
    size_t  numElements = 0;
    size_t  numLines = 0;
    result = getNumberOfElementsAndLines(&numElements, &numLines);

    long*   a = NULL;
    long*   b = NULL;
    if (result == 1)
    {
        result = allocateAndInitArrays(numElements, &a, &b);
    }

    if (result == 1)
    {
        result = getAndProcessInput(a, b, numElements, numLines);
    }

    free(a);
    free(b);

    return result;
}

Memory

You'll notice above that I used calloc() to allocate the memory on the heap instead of the stack. Stack space is limited, and there's a lot more memory available on the heap. That may fix your issue getting a segfault.

Error Handling

I added a little bit of error handling. It needs more. You should check to make sure you got valid results from functions like scanf(), for example. What if the user entered a negative number? What if they entered 0? Etc.

StackExchange Code Review Q#104515, answer score: 5