LeetCode 3100 - Water Bottles II

Difficulty: 🟡 Medium
Topics: Math, Simulation

Solution

Problem Understanding

This problem models a bottle exchange process where the exchange rate increases after every successful trade.

You start with numBottles full water bottles. Every time you drink a full bottle, it becomes an empty bottle. Empty bottles can then be exchanged for new full bottles, but there is an important rule: after each exchange, the required number of empty bottles increases by one.

For example, if the current exchange cost is 3, you may trade exactly 3 empty bottles for 1 full bottle. After completing that exchange, the next exchange will require 4 empty bottles, then 5, and so on.

The goal is to compute the maximum total number of bottles you can drink.

The input consists of two integers:

numBottles, the number of full bottles initially available
numExchange, the starting exchange cost

The output is a single integer representing the total number of bottles drunk after performing the best possible sequence of drinking and exchanges.

The constraints are small:

1 <= numBottles <= 100
1 <= numExchange <= 100

These limits tell us several useful things:

The simulation will always terminate quickly.
We do not need advanced optimization techniques.
A direct step-by-step simulation is completely acceptable.

There are several important edge cases to keep in mind.

If numExchange is larger than the total number of empty bottles you can ever accumulate, then no exchanges are possible. In that case, the answer is simply the initial number of bottles.

If numExchange == 1, the first exchange is extremely cheap. However, after the first trade, the cost becomes 2, then 3, and so on. A naive implementation might incorrectly allow multiple exchanges at the same cost.

Another subtle point is that after each exchange, you immediately gain another full bottle, which can later become another empty bottle after drinking it. The simulation must carefully maintain both the empty bottle count and the changing exchange cost.

Approaches

Brute Force Approach

The brute-force idea is to simulate every operation literally.

We begin with all bottles full. We drink every available full bottle, increasing the empty bottle count and the total number of bottles consumed.

Then, while we have enough empty bottles to perform an exchange, we trade the required number of empty bottles for one new full bottle. After the exchange:

the number of empty bottles decreases by the current exchange cost
the exchange cost increases by one
the new full bottle is immediately available to drink

This process repeats until we can no longer afford another exchange.

This approach is correct because the problem is deterministic. There is never a strategic choice to make. Drinking bottles earlier or later produces the same result because empty bottles are the only resource that matters.

Although this simulation is sometimes called "brute force," it is already efficient enough because the constraints are very small.

Key Insight

The important observation is that the process is entirely greedy and linear.

At every moment:

drinking bottles is always beneficial
exchanging bottles whenever possible is always optimal
there is no advantage in delaying an exchange

That means we only need a single simulation loop.

Instead of exploring different possibilities, we repeatedly perform the only valid action:

Drink all currently available bottles.
Exchange empty bottles whenever possible.
Increase the exchange requirement after every trade.

This yields a clean and optimal simulation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(answer)	O(1)	Simulates every bottle consumed and every exchange
Optimal	O(answer)	O(1)	Same simulation, but expressed cleanly as a direct greedy process

Algorithm Walkthrough

Initialize the total number of bottles drunk with numBottles.

At the beginning, all bottles are full and can eventually be consumed, so we immediately count them toward the answer. 2. Initialize the number of empty bottles.

After drinking the initial bottles, we will have exactly numBottles empty bottles available. 3. Repeatedly check whether another exchange is possible.

As long as the current number of empty bottles is at least numExchange, we may perform another trade. 4. Perform the exchange.

We spend numExchange empty bottles to obtain one full bottle.

This reduces the empty bottle count by numExchange. 5. Increase the exchange requirement.

After each successful trade, the problem states that the exchange cost increases by one. 6. Drink the newly obtained bottle.

Drinking the new bottle increases the total number of bottles drunk by one.

It also creates one additional empty bottle, so we add one back to the empty bottle count. 7. Continue until no exchange is possible.

Once the empty bottle count becomes smaller than the current exchange requirement, the process stops. 8. Return the total number of bottles drunk.

Why it works

The algorithm works because the process is deterministic and greedy.

Every full bottle should always be drunk immediately because drinking only increases the number of empty bottles available for future exchanges. Similarly, every possible exchange should always be taken because exchanges strictly increase the total number of bottles consumed.

At every iteration, the algorithm maintains the invariant that:

empty_bottles equals the number of currently available empty bottles
total_drunk equals the number of bottles consumed so far
numExchange equals the current exchange cost

Since each loop iteration exactly matches one valid exchange operation from the problem statement, the final result is guaranteed to be correct.

Python Solution

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

        while empty_bottles >= numExchange:
            empty_bottles -= numExchange
            numExchange += 1

            total_drunk += 1
            empty_bottles += 1

        return total_drunk

The implementation directly follows the simulation described earlier.

The variable total_drunk stores the total number of bottles consumed so far. Initially, this equals the number of full bottles we start with.

The variable empty_bottles tracks how many empty bottles are currently available for exchanges. Since drinking the initial bottles creates empty bottles, this also starts at numBottles.

The while loop continues as long as another exchange is possible.

Inside the loop:

we spend numExchange empty bottles
we increase the exchange cost by one
we drink the newly acquired bottle
we gain one new empty bottle from drinking it

When the loop ends, no more exchanges are possible, so the accumulated total is returned.

Go Solution

func maxBottlesDrunk(numBottles int, numExchange int) int {
    totalDrunk := numBottles
    emptyBottles := numBottles

    for emptyBottles >= numExchange {
        emptyBottles -= numExchange
        numExchange++

        totalDrunk++
        emptyBottles++
    }

    return totalDrunk
}

The Go implementation mirrors the Python solution almost exactly.

Go uses explicit variable declarations with :=, and the loop is written using Go's for syntax instead of Python's while.

Integer overflow is not a concern because the constraints are extremely small. No additional data structures are required, so the solution uses constant extra space.

Worked Examples

Example 1

Input:

numBottles = 13
numExchange = 6

Initial state:

Total drunk = 13
Empty bottles = 13
Exchange cost = 6

Step	Empty Bottles Before	Exchange Cost	Can Exchange?	Empty Bottles After Exchange	Empty Bottles After Drinking	Total Drunk
Initial	13	6	Yes	7	8	14
2	8	7	Yes	1	2	15
End	2	8	No	-	-	15

Final answer:

Example 2

Input:

numBottles = 10
numExchange = 3

Initial state:

Total drunk = 10
Empty bottles = 10
Exchange cost = 3

Step	Empty Bottles Before	Exchange Cost	Can Exchange?	Empty Bottles After Exchange	Empty Bottles After Drinking	Total Drunk
Initial	10	3	Yes	7	8	11
2	8	4	Yes	4	5	12
3	5	5	Yes	0	1	13
End	1	6	No	-	-	13

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(answer)	Each loop iteration corresponds to one successful exchange
Space	O(1)	Only a few integer variables are used

The running time depends on the number of exchanges performed. Since every exchange increases the required cost, the loop terminates quickly. Under the given constraints, the number of iterations is very small.

The algorithm uses constant extra memory because it stores only counters and does not allocate additional data structures.

Test Cases

solution = Solution()

assert solution.maxBottlesDrunk(13, 6) == 15  # Provided example 1
assert solution.maxBottlesDrunk(10, 3) == 13  # Provided example 2

assert solution.maxBottlesDrunk(1, 1) == 2  # Smallest values with one exchange
assert solution.maxBottlesDrunk(1, 2) == 1  # Cannot exchange at all
assert solution.maxBottlesDrunk(2, 1) == 3  # Immediate cheap exchange
assert solution.maxBottlesDrunk(3, 1) == 5  # Multiple increasing exchanges
assert solution.maxBottlesDrunk(5, 10) == 5  # Exchange cost too high
assert solution.maxBottlesDrunk(100, 1) == 113  # Large input with many exchanges
assert solution.maxBottlesDrunk(100, 100) == 101  # Exactly one exchange possible
assert solution.maxBottlesDrunk(15, 4) == 18  # Several sequential exchanges

Test	Why
`(13, 6)`	Validates the first official example
`(10, 3)`	Validates the second official example
`(1, 1)`	Tests smallest possible exchange threshold
`(1, 2)`	Tests scenario with no exchanges
`(2, 1)`	Tests immediate exchange behavior
`(3, 1)`	Tests repeated increasing exchange costs
`(5, 10)`	Tests when exchange requirement is unreachable
`(100, 1)`	Stress test with many exchanges
`(100, 100)`	Tests boundary where exactly one exchange is possible
`(15, 4)`	Tests multiple successful exchanges

Edge Cases

One important edge case occurs when the exchange cost is larger than the number of bottles available. For example, numBottles = 5 and numExchange = 10. In this scenario, no exchange can ever happen. A buggy implementation might still attempt exchanges or incorrectly update counters. The solution handles this correctly because the while condition fails immediately.

Another subtle case is when numExchange = 1. The first exchange becomes free in terms of bottle accumulation because one empty bottle immediately produces another full bottle. However, the exchange cost must increase after every trade. Incorrect implementations sometimes allow repeated exchanges at the same cost, which produces an infinite loop. This solution avoids that by incrementing numExchange after every successful exchange.

A third important edge case is when the empty bottle count exactly matches the exchange cost. For example, numBottles = 100 and numExchange = 100. The algorithm must allow that final exchange because the condition is >=, not >. After the trade, the empty bottle count drops below the next required exchange value, so the process terminates naturally.

A final edge case involves very small inputs such as numBottles = 1. Small values often expose off-by-one mistakes in simulations. The implementation correctly initializes both the total bottles drunk and the empty bottle count using the initial number of bottles, ensuring the process begins in the correct state.