4
\$\begingroup\$

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;
        }        
    }
}
\$\endgroup\$
  • 7
    \$\begingroup\$ The task is not very clear to me. I recommend adding 2-3 pairs of example inputs and expected outputs, and also to include the link to the original challenge \$\endgroup\$ – janos Jul 9 '16 at 11:22
  • 2
    \$\begingroup\$ I feel compelled to point out that the plural of 'Index' is 'Indices' not 'Indexes'. Also that question is really badly worded, I've read it 3 times and still have no idea what it's supposed to be asking. \$\endgroup\$ – Pharap Jul 9 '16 at 14:46
  • \$\begingroup\$ @Pharap Both plurals are acceptable. \$\endgroup\$ – 200_success Jul 9 '16 at 18:17
  • \$\begingroup\$ @200_success "especially in technical use" If programming isn't technical, I don't know what is. "spelled indices (as in the original Latin) in subjects like science" computer science is still science. \$\endgroup\$ – Pharap Jul 9 '16 at 18:44
  • \$\begingroup\$ @Pharap Insisting on "indices" is for all technical use is not justified, though. There are also plenty of other users on this site that you could harass, but shouldn't. \$\endgroup\$ – 200_success Jul 9 '16 at 18:57
13
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ using namespace std; isn't bad practice in itself, there are times where it's completely safe. If the op moved it to the start of main so it shared main's scope, it wouldn't be an issue. \$\endgroup\$ – Pharap Jul 9 '16 at 14:53
  • 1
    \$\begingroup\$ @Pharap thanks, I rephrased that to be more accurate, with a link to more detailed info \$\endgroup\$ – janos Jul 9 '16 at 15:11
  • \$\begingroup\$ I'm really new here, so please bare with my mistakes. Thanks a lot for suggesting the solution. \$\endgroup\$ – Raghav Raghavendra Jul 10 '16 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.