Problem Statement in English

You’re given two integers numBottles and numExchange. You have numBottles full water bottles. You can exchange numExchange empty water bottles for one full water bottle.

Return the maximum number of water bottles you can drink.

Note: You can only exchange numExchange empty bottles at a time.

Approach

This is a straightforward implementation problem.

Solution in Python


class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        f = numBottles
        e = res = 0

        while f or e >= numExchange:
            if e >= numExchange:
                f += 1
                e -= numExchange
                numExchange += 1
            else:
                res += f
                e += f
                f = 0
        
        return res

Complexity

  • Time: $O(n+m)$
    Here, n is the number of full bottles and m is the number of empty bottles. In the worst case, we may need to process each bottle multiple times.

  • Space: $O(1)$
    We are using a constant amount of space for the variables f, e, and res.

And we are done.