Problem Link:Difficulty:EasyMediumPrerequisites:Binary SearchProblem:Find the maximum number x for which the sum of x natural numbers don't exceeds the litres of water available.Explanation:Given that the first bucket has a capacity of 1 litre, second bucket has capacity of 2 litres and so on. So we just need the maximum number x so that $1+2+3+....+x <=n$, where n is the litres of the water available. Thus, problem is a searching problem, we are just searching for the required x.First approach is we can use linear search to find the value of x but it will exceed the time limit. So, we have to think of a more efficient searching approach. Next approach is to use the binary search as it is very efficient and very well within the time limit of the problem. Solution:Author's solution can be found here. asked 11 May '17, 08:24

Why can't we just use the formula for Sum of first n natural numbers? (n*(n+1))/2 = N This was mine, I don't know why I was getting TLE. I mean, I'm okay with getting a wrong answer (I just reread the question and saw the line, "The bucket will be considered filled if it has atleast 1 litre in it.") But why am I getting a TLE? Is the sqrt() function that heavy/slow? answered 11 May '17, 11:27
It is because the problem is not that easy. The time limit of the problem is very less. So you can't use the linear approach. The problem was designed that way.
(12 May '17, 14:35)

import math for t in range(input()): s=int(raw_input()) a=1 b=1 c=2s d=b24ac if d>0: x1=b+math.sqrt(d) x1=x1/2a print int(math.ceil(x1)) answered 11 May '17, 15:40

Hi. See in line 22, you should be checking for <=N (you did <N instead). + in line 22's "if" satisfies, i.e mid * (mid1) / 2 <= N, then the result var should be set to mid1 (you did mid instead). Hope it helps. answered 29 May '17, 01:34
