AlgoVisual | See the logic

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

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

13 return res

Water Refilling

Reference solution