Problem Description

You start with numBottles full water bottles. After drinking a bottle, it becomes empty. You can trade numExchange empty bottles at the market to get 1 new full bottle.

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

For example, if you start with numBottles = 9 and numExchange = 3:

• First, drink all 9 bottles (total drunk: 9, empty bottles: 9)
• Exchange 9 empty bottles for 3 new full bottles (since 9 ÷ 3 = 3)
• Drink these 3 bottles (total drunk: 12, empty bottles: 3)
• Exchange 3 empty bottles for 1 new full bottle (since 3 ÷ 3 = 1)
• Drink this 1 bottle (total drunk: 13, empty bottles: 1)
• Can't exchange anymore since 1 < 3

The solution uses a clever approach: instead of simulating the full exchange process, it recognizes that each exchange of numExchange empty bottles gives us 1 full bottle, which effectively reduces our empty bottle count by numExchange - 1 (we lose numExchange empties but gain 1 that becomes empty after drinking). The loop continues exchanging and drinking while we have enough empty bottles to trade.

Intuition

The key insight is understanding what happens during each exchange cycle. When we trade numExchange empty bottles for 1 full bottle, we're essentially converting numExchange empties into 1 empty (after drinking the full one we got). This means we net a reduction of numExchange - 1 empty bottles while drinking 1 more bottle.

Think of it this way: if we have exactly numExchange empty bottles, we can:

1. Trade them for 1 full bottle
2. Drink that bottle (adding 1 to our answer)
3. End up with 1 empty bottle

So we went from numExchange empties to 1 empty, a reduction of numExchange - 1.

This pattern continues as long as we have at least numExchange empty bottles to trade. Each iteration:

• Decreases our empty bottle count by numExchange - 1
• Increases our drunk bottle count by 1

Instead of tracking empty and full bottles separately through multiple exchanges and drinking cycles, we can simplify: start with drinking all initial bottles (that's our starting ans = numBottles), then keep exchanging and drinking one at a time by reducing our bottle count by numExchange - 1 each round.

The elegance of numBottles -= numExchange - 1 is that it directly computes how many empty bottles remain after one complete exchange-and-drink cycle, avoiding the need to simulate the actual exchange process step by step.

Learn more about Math patterns.

Solution Approach

The implementation uses a greedy simulation approach with a mathematical optimization.

Algorithm Steps:

1. Initialize the answer: Start with ans = numBottles since we can immediately drink all the initial bottles.

2. Simulation loop: While we have enough empty bottles to make an exchange (numBottles >= numExchange):

   • Perform one exchange cycle by updating numBottles -= numExchange - 1
     • This represents trading numExchange empties for 1 full bottle, drinking it, and keeping the resulting empty
   • Increment the answer by 1 for the bottle we just drank: ans += 1

3. Return the result: Once we can't exchange anymore (when numBottles < numExchange), return ans

Why this works:

The formula numBottles -= numExchange - 1 is the mathematical representation of one complete exchange cycle:

• We start with numBottles empty bottles
• We use numExchange of them to get 1 full bottle
• After drinking, we have numBottles - numExchange + 1 empty bottles
• This simplifies to numBottles - (numExchange - 1)

Time Complexity: O(numBottles / numExchange) - The loop runs approximately numBottles / (numExchange - 1) times since each iteration reduces bottles by numExchange - 1.

Space Complexity: O(1) - We only use a constant amount of extra space for variables.

The beauty of this solution is that it avoids explicitly tracking full and empty bottles separately, instead maintaining just the count of bottles available for exchange after each drinking cycle.

Example Walkthrough

Let's trace through an example with numBottles = 10 and numExchange = 3:

Initial State:

• Start with 10 full bottles
• Drink all 10 bottles immediately → ans = 10
• Now we have 10 empty bottles → numBottles = 10

First Exchange Cycle:

• Check: Can we exchange? 10 >= 3 ✓ Yes
• Trade 3 empties for 1 full, drink it, keep the empty
• Update: numBottles = 10 - (3 - 1) = 8 empty bottles remain
• Update: ans = 10 + 1 = 11 total drunk

Second Exchange Cycle:

• Check: Can we exchange? 8 >= 3 ✓ Yes
• Trade 3 empties for 1 full, drink it, keep the empty
• Update: numBottles = 8 - (3 - 1) = 6 empty bottles remain
• Update: ans = 11 + 1 = 12 total drunk

Third Exchange Cycle:

• Check: Can we exchange? 6 >= 3 ✓ Yes
• Trade 3 empties for 1 full, drink it, keep the empty
• Update: numBottles = 6 - (3 - 1) = 4 empty bottles remain
• Update: ans = 12 + 1 = 13 total drunk

Fourth Exchange Cycle:

• Check: Can we exchange? 4 >= 3 ✓ Yes
• Trade 3 empties for 1 full, drink it, keep the empty
• Update: numBottles = 4 - (3 - 1) = 2 empty bottles remain
• Update: ans = 13 + 1 = 14 total drunk

Termination:

• Check: Can we exchange? 2 >= 3 ✗ No
• Stop the loop
• Final answer: 14 bottles drunk

The key insight: Each cycle effectively converts numExchange empty bottles into 1 drunk bottle plus 1 empty bottle, reducing our empty count by exactly numExchange - 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(numBottles / numExchange) or simplified to O(n/m) where n is the initial number of bottles and m is the exchange rate.

The while loop continues as long as numBottles >= numExchange. In each iteration, numBottles decreases by (numExchange - 1). The number of iterations can be calculated as approximately numBottles / (numExchange - 1). Since numExchange ≥ 2 (based on problem constraints), the worst case would be when numExchange = 2, giving us O(numBottles) iterations. In the general case, it's O(numBottles / numExchange).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It modifies the input variable numBottles and maintains one additional variable ans to track the total number of bottles drunk. No additional data structures or recursive calls are used, so the space complexity remains constant regardless of input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Different Approaches

A common alternative approach involves calculating the total mathematically using the formula: numBottles + (numBottles - 1) / (numExchange - 1). This can cause integer overflow for large values of numBottles when numExchange = 2, since we're essentially computing numBottles + numBottles - 1.

Pitfall Example:

# Problematic mathematical approach
def numWaterBottles(numBottles: int, numExchange: int) -> int:
    if numExchange == 2:
        return numBottles * 2 - 1  # Can overflow for large numBottles
    return numBottles + (numBottles - 1) // (numExchange - 1)

Solution: Stick with the iterative simulation approach which naturally handles large numbers without overflow risks.

2. Incorrect Loop Termination Condition

Developers might mistakenly use numBottles > numExchange instead of numBottles >= numExchange, missing the case where we have exactly numExchange empty bottles.

Pitfall Example:

while numBottles > numExchange:  # Wrong! Misses the equality case
    numBottles -= numExchange - 1
    total_drunk += 1

Solution: Use >= to ensure we exchange when we have exactly numExchange bottles:

while numBottles >= numExchange:  # Correct
    numBottles -= numExchange - 1
    total_drunk += 1

3. Misunderstanding the Exchange Logic

Some might incorrectly implement the exchange as dividing bottles by numExchange and adding all obtained bottles at once, forgetting that newly obtained bottles also become empty and can be exchanged again.

Pitfall Example:

def numWaterBottles(numBottles: int, numExchange: int) -> int:
    total = numBottles
    empty = numBottles
    new_bottles = empty // numExchange  # Gets all possible exchanges at once
    total += new_bottles  # Wrong! Doesn't account for recursive exchanges
    return total

Solution: Process exchanges one at a time or properly handle the recursive nature:

def numWaterBottles(numBottles: int, numExchange: int) -> int:
    total = numBottles
    empty = numBottles
  
    while empty >= numExchange:
        new_bottles = empty // numExchange
        total += new_bottles
        empty = empty % numExchange + new_bottles  # Correctly track remaining empties
  
    return total

4. Edge Case: numExchange = 1

While typically not a valid input (would lead to infinite bottles), if numExchange = 1 appears, the current solution would enter an infinite loop since numBottles never decreases.

Solution: Add validation or handle this edge case explicitly:

def numWaterBottles(numBottles: int, numExchange: int) -> int:
    if numExchange == 1:
        return float('inf')  # Or handle according to problem constraints
  
    total_drunk = numBottles
    while numBottles >= numExchange:
        numBottles -= numExchange - 1
        total_drunk += 1
  
    return total_drunk