Code Implementation

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
      

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int total = numBottles;
        int empty = numBottles;
        while (empty >= numExchange) {
            int new_bottles = empty / numExchange;
            total += new_bottles;
            empty = empty % numExchange + new_bottles;
        }
        return total;
    }
};
      

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int total = numBottles;
        int empty = numBottles;
        while (empty >= numExchange) {
            int newBottles = empty / numExchange;
            total += newBottles;
            empty = empty % numExchange + newBottles;
        }
        return total;
    }
}
      

var numWaterBottles = function(numBottles, numExchange) {
    let total = numBottles;
    let empty = numBottles;
    while (empty >= numExchange) {
        let newBottles = Math.floor(empty / numExchange);
        total += newBottles;
        empty = empty % numExchange + newBottles;
    }
    return total;
};
      

Problem Description

You are given two integers: numBottles, the number of full water bottles you initially have, and numExchange, the number of empty bottles required to exchange for one full bottle. Each time you drink a bottle, you gain an empty bottle. You can exchange empty bottles for full ones as long as you have at least numExchange empty bottles. Your task is to calculate the maximum number of water bottles you can drink.

Key constraints:

• You can only exchange empty bottles for full ones if you have at least numExchange empty bottles.
• Each exchange gives you exactly one full bottle.
• All bottles are identical, and you cannot reuse full bottles without drinking them first.
• Return the total number of bottles you can drink, including those obtained via exchange.

Thought Process

At first glance, the problem seems straightforward: drink all your bottles, then exchange the empty ones for more, and repeat. But to maximize the total number of bottles drunk, you need to keep track of how many empty bottles you have after each exchange and continue as long as possible.

The brute-force approach is to simulate the process step by step: after drinking all current bottles, check if you have enough empty bottles to exchange for new ones, and repeat. The process ends when you can no longer exchange. However, we can optimize this by noticing a pattern: in each round, you exchange as many times as possible, and the number of bottles you can drink increases by the number of exchanges.

The key insight is to keep a running total of bottles drunk and keep updating the count of empty bottles after each exchange, always using as many exchanges as possible in each round.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize your counters:
   • Set total to numBottles (the bottles you start with).
   • Set empty to numBottles (since you'll have that many empty bottles after drinking).
2. Loop while exchanges are possible:
   • While empty >= numExchange, do the following:
   • Calculate new_bottles = empty // numExchange (how many new bottles you get this round).
   • Add new_bottles to total (since you'll drink them too).
   • Update empty to empty % numExchange + new_bottles (leftover empties plus the new empties you get after drinking the exchanged bottles).
3. Return the result:
   • When you can no longer exchange, return total as the answer.

Example Walkthrough

Let's use numBottles = 9 and numExchange = 3 as our sample input.

1. Start: You have 9 full bottles, so you drink 9 and get 9 empty bottles.
2. First Exchange: You can exchange 9 // 3 = 3 times, getting 3 new full bottles. Now, total = 9 + 3 = 12. After drinking, you have 3 new empties + 0 leftover (since 9 % 3 = 0), so 3 empty bottles.
3. Second Exchange: With 3 empty bottles, you can exchange 3 // 3 = 1 time, getting 1 more full bottle. Now, total = 12 + 1 = 13. After drinking, you have 1 new empty + 0 leftover, so 1 empty bottle.
4. No More Exchanges: You only have 1 empty bottle left, which is less than numExchange. So you're done.

Final Answer: 13 bottles.

Time and Space Complexity

Brute-force approach: In the naive approach, you might simulate each bottle exchange individually, which would take O(total bottles) time, but our optimized approach is much faster.

Optimized approach: Each iteration reduces the number of empty bottles by a factor of numExchange, so the number of iterations is about log_numExchange(numBottles). In practice, since numBottles drops quickly, the loop runs a small number of times. Thus, the time complexity is O(log n), where n is numBottles.

Space complexity: O(1) extra space, since we use only a few integer variables.

Summary

The Water Bottles problem is a classic simulation with a greedy flavor: always exchange as many empty bottles as possible in each step. By tracking the total drunk and the number of empty bottles, we efficiently find the answer with a simple loop. The key insight is that each round of exchanges can be calculated in bulk, and the process continues until exchanges are no longer possible. This makes the solution both elegant and efficient, with O(1) space and logarithmic time.