can anyone give a hint to solve this problem?

Any hint to solve this problem?

You can use a prefix sum array and binary search to solve it in \mathcal{O}(n \log n). Since you asked for a hint, Iā€™m not giving further details. You can also solve it in \mathcal{O}(n) with a little more clever thinking, and this way is described in the tutorial.
I can elaborate further if you get stuck, good luck :slight_smile:

1 Like

I have solved problems on prefix sums and brute force but how to apply binary search to it

for i:array
for j:i+1 to end
find a=do binary search for s/3
find b=do binary search for 2s/3
cnt+=1
kindly correct this answer

Let the sum of the whole array be S. If you find a valid i upto which the prefix sum is \frac{S}{3}, you can binary search the prefix sum array for the range where the values are \frac{2S}{3}, and those will be valid choices of j.

do we have to do upper bound-lower bound for 2s/3

Yes, exactly. If you are using C++ there is also the equal_range function.

Thanks for your help.

No problem!