 Given a tank with capacity C liters which is completely filled in starting. Everyday tank is filled with l liters of water and in the case of overflow extra water is thrown out. Now on i-th day i liters of water is taken out for drinking. We need to find out the day at which tank will become empty the first time.

### Manual Synopsis

Input : Capacity = 5
l = 2
Output : 4
At the start of 1st day, water in tank = 5
and at the end of the 1st day = (5 – 1) = 4
At the start of 2nd day, water in tank = 4 + 2 = 6
but tank capacity is 5 so water = 5
and at the end of the 2nd day = (5 – 2) = 3
At the start of 3rd day, water in tank = 3 + 2 = 5
and at the end of the 3rd day = (5 – 3) = 2
At the start of 4th day, water in tank = 2 + 2 = 4
and at the end of the 4th day = (4 – 4) = 0
So final answer will be 4

### Code

# Python3 code to find number of days
# after which tank will become empty

# Utility method to get
# sum of first n numbers
def getCumulateSum(n):

return int((n * (n + 1)) / 2)

# Method returns minimum number of days
# after which tank will become empty
def minDaysToEmpty(C, l):

# if water filling is more than
# capacity then after C days only
# tank will become empty
if (C <= l) : return C

# initialize binary search variable
lo, hi = 0, 1e4

# loop until low is less than high
while (lo < hi):
mid = int((lo + hi) / 2)

# if cumulate sum is greater than (C - l)
# then search on left side
if (getCumulateSum(mid) >= (C - l)):
hi = mid

# if (C - l) is more then
# search on right side
else:
lo = mid + 1

# Final answer will be obtained by
# adding l to binary search result
return (l + lo)

# Driver code
C, l = 5, 2
print(minDaysToEmpty(C, l))

# This code is contributed by Smitha Dinesh Semwal.



We can see that tank will be full for starting (l + 1) days because water taken out is less than water being filled. After that, each day water in the tank will be decreased by 1 more liter and on (l + 1 + i)th day (C – (i)(i + 1) / 2) liter water will remain before taking drinking water.
Now we need to find a minimal day (l + 1 + K), in which even after filling the tank by l liters we have water less than l in tank i.e. on (l + 1 + K – 1)th day tank becomes empty so our goal is to find minimum K such that,
C – K(K + 1) / 2 <= l

We can solve above equation using binary search and then (l + K) will be our answer. Total time complexity of solution will be O(log C)

Output:

4


Alternate Solution :
It can be solved mathematically with a simple formula:

Let’s Assume C>L. Let d be the amount of days after the Lth when the tank become empty.During that time, there will be (d-1)refills and d withdrawals.
Hence we need to solve this equation : Sum of all withdrawals is a sum of arithmetic progression,therefore :   Discriminant = 1+8(C-L)>0,because C>L.
Skipping the negative root, we get the following formula: Therefore, the final alwer is: # Python3 code to find number of days
# after which tank will become empty
import math

# Method returns minimum number of days
# after which tank will become empty
def minDaysToEmpty(C, l):

if (l >= C): return C

eq_root = (math.sqrt(1 + 8 * (C - l)) - 1) / 2
return math.ceil(eq_root) + l

# Driver code
print(minDaysToEmpty(5, 2))
print(minDaysToEmpty(6514683, 4965))

# This code is contributed by Smitha Dinesh Semwal.



Thanks to Andrey Khayrutdinov for suggesting this solution.