Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Drink all initially full bottles first. Thereafter each successful exchange produces one more drink and returns one empty bottle, while the next exchange becomes more expensive. Tracking only empty bottles and the current exchange price is enough.

Approach

Initialize the answer to the initial bottle count and treat that count as the number of empties now available. While there are at least as many empties as the current price, spend that many empties, increase the price by one, drink the received bottle, and add its empty bottle back. Increment the answer for that drink.

When the current price cannot be paid, no further exchange is possible. Performing an affordable exchange cannot lose an opportunity to obtain more drinks, since there is only one exchange option and its price increases only when it is used. Return the accumulated count.

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

        while numBottles >= numExchange:
            numBottles -= numExchange
            numExchange += 1
            numBottles += 1
            res += 1

        return res

Complexity analysis

Let B be the initial bottle count. Time: O(sqrt(B)) in the worst case (one loop per successful exchange). Auxiliary space: O(1).