Water Bottles

Difficulty: Easy | Acceptance: 72.60% | Paid: No Topics: Math, Simulation

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

• Examples
• Constraints
• Simulation
• Mathematical Formula
• Recursive

Examples

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full bottle.
Number of drunk bottles:
- Drink 9 full bottles, get 9 empty bottles.
- Exchange 9 empty bottles for 3 full bottles.
- Drink 3 full bottles, get 3 empty bottles.
- Exchange 3 empty bottles for 1 full bottle.
- Drink 1 full bottle, get 1 empty bottle.
Total: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full bottle.
Number of drunk bottles:
- Drink 15 full bottles, get 15 empty bottles.
- Exchange 12 empty bottles for 3 full bottles, 3 empty remain.
- Drink 3 full bottles, get 3 empty bottles, now 6 empty.
- Exchange 4 empty bottles for 1 full bottle, 2 empty remain.
- Drink 1 full bottle, get 1 empty bottle, now 3 empty.
Total: 15 + 3 + 1 = 19.

Constraints

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

Simulation

Intuition Simulate the process of drinking bottles and exchanging empty ones for full ones until we can no longer exchange.

Steps

• Initialize total with numBottles (we drink all initial bottles)
• Initialize empty with numBottles
• While empty >= numExchange:
  • Calculate how many new bottles we get from exchange
  • Add new bottles to total
  • Update empty bottles (remaining + new bottles)
• Return total

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        total = numBottles
        empty = numBottles
        
        while empty >= numExchange:
            new_bottles = empty // numExchange
            total += new_bottles
            empty = empty % numExchange + new_bottles
        
        return total

Complexity

• Time: O(log(numBottles)) - each iteration reduces the number of bottles
• Space: O(1) - only using constant extra space
• Notes: Simple and intuitive approach

Mathematical Formula

Intuition The problem can be solved with a direct formula: total = numBottles + floor((numBottles - 1) / (numExchange - 1)). This formula accounts for all exchanges in one calculation.

Steps

• If numExchange is 1, we can exchange infinitely, but constraints prevent this
• Apply the formula: numBottles + (numBottles - 1) / (numExchange - 1)
• Return the result

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        return numBottles + (numBottles - 1) // (numExchange - 1)

Complexity

• Time: O(1) - single calculation
• Space: O(1) - no extra space needed
• Notes: Most efficient solution but requires understanding the mathematical insight

Recursive

Intuition Recursively solve by drinking all current bottles, then exchanging empty bottles for new ones and continuing.

Steps

• Base case: if numBottles < numExchange, return numBottles
• Calculate new bottles from exchange and remaining empty bottles
• Recursively solve with the new total of bottles

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        if numBottles < numExchange:
            return numBottles
        
        new_bottles = numBottles // numExchange
        remaining = numBottles % numExchange
        
        return numBottles + self.numWaterBottles(new_bottles + remaining, numExchange)

Complexity

• Time: O(log(numBottles)) - each recursive call reduces the problem size
• Space: O(log(numBottles)) - recursion stack depth
• Notes: Elegant but uses stack space; can be converted to iterative