Guess the chocolate box

Question

I'm new to this competitive programming world. This morning I came across this question, which required the time to be less than 1 sec. But my code runs for 1.000069 sec, thereby rejecting my solution.

Question:

There are N chocolate boxes, and you will be given with a chocolate index for which we have to guess the correct box number. For example, The first box contain chocolates from 1 to N1 and the next box contain N1+1 through N2 and so on.

My Solution:

#include<iostream>
using namespace std;

//returns the sum of chocolates from 0 to i 

int getSum(int i,int *array){
    int sum = 0;
    for(int j=0; j< i; j++){
        sum += array[j];
    }
    return sum;
}
int main(){
    int n,q;
    //Get the number of chocolate boxes.
    cin >> n;  
    int chocolatesInEachBox[n];     
    //Get the number of chocolates in each box.
    for(int i =0; i < n; i++){
        cin >> chocolatesInEachBox[i];
    }   
    //Get the number of queries.
    cin>>q;
    int chocolateIndexes[q];
    //Get each query.
    for(int i =0; i < q; i++){
        cin >> chocolateIndexes[i];
    }
    int j=0,i=0;

    while(j < q && i<n){

        if((chocolateIndexes[j]-getSum(i+1,chocolatesInEachBox))>0)
        i++;

        else{
            cout<<i+1<<endl;
            j++;
            i=0;
        }        
    }
}

Answer 1

Performance

The getSum function calculates the sum of the values in the given array up to the specified index. As you calculate the result to multiple queries, each using the same array as the parameter, the same calculation is repeated multiple times, which is certainly the cause of the slowness. The time complexity of getSum is \$O(n)\$, and of the entire solution it's \$O(n^2)\$.

You could improve the performance greatly by pre-computing an array of so-called prefix sums: the sums of elements up to each index. For example if the input array contains 7 3 1 5 5 then the array of prefix sums will contain 0 7 10 11 16 21. This can be done in a single pass, in \$O(n)\$ time.

With this change, the time complexity of getSum would become \$O(1)\$, and of the entire solution \$O(n)\$, significantly faster than the original solution.

Style issues

Try to organize your program into multiple functions with a single responsibility. Like getSum, that was well done, but the rest of the program should be split up to smaller logical units.

In C++ you don't need to declare variables at the top of functions, like you did for q. It's better to declare right before you need it.

Lastly, note that using namespace std is generally not recommended.