Water Refilling

We have an empty container with a capacity of a gallons of water and another container with a capacity of b gallons. Return how many times you can pour the second container full of water into the first one without overflowing. Assume that a > b.

Constraint: You are not allowed to use the division operation, but you can use still divide by powers of two with the right-shift operator, >>. Recall that x >> 1 is the same as x // 2.

Example:

  • Input: a = 18, b = 5
  • Output: 3 (53 = 15 <= 18, but 54 = 20 > 18)
1def waterRefilling(a: int, b: int) -> int:
2    l, r = 0, a # Max possible is a if b=1
3    res = 0
4    
5    while l <= r:
6        mid = (l + r) >> 1
7        if mid * b <= a:
8            res = mid
9            l = mid + 1
10        else:
11            r = mid - 1
12            
13    return res
Previous
Min-Subarray-Sum Split
Next
Min Pages Per Day
a=18
b=5
Step 1 / 6
Step 1:
Search range [0, 18]. a=18, b=5.
Pointers: l=0, mid=9, r=18
Focus: default
a=18b=5