Water Bottles - Video Solutions

Problem Overview: You start with numBottles full water bottles. After drinking a bottle you keep the empty one. Every numExchange empty bottles can be traded for one new full bottle. The task is to compute the maximum number of bottles you can drink.

The core idea is simple: every bottle eventually becomes an empty bottle that may help you obtain another full bottle. The challenge is tracking how exchanges accumulate over time.

Approach 1: Iterative Simulation (Time: O(n), Space: O(1))

This approach directly models the process described in the problem. Start by drinking all numBottles, which gives you the same number of empty bottles. As long as you have at least numExchange empties, exchange them for new full bottles. Each exchange increases the total bottles drunk and updates the empty bottle count.

The implementation uses a loop: compute how many new bottles you can obtain with integer division, add them to the total consumed, and update the remaining empties using modulo plus the new empties created by drinking. This is a classic simulation pattern where the code mirrors the real-world process step by step.

This method is easy to reason about and safe for interviews. Time complexity is O(n) where n is roughly the number of bottles consumed through exchanges, and space complexity is O(1) since only a few counters are maintained.

Approach 2: Mathematical Approach (Time: O(1), Space: O(1))

Instead of simulating every exchange, observe the pattern of bottle consumption. Every time you exchange bottles, you effectively spend numExchange empty bottles to gain one full bottle, but after drinking it you get one empty bottle back. The net cost of producing one extra drink becomes numExchange - 1 empty bottles.

This leads to a compact formula. Starting with numBottles bottles, the number of additional bottles you can drink through exchanges is (numBottles - 1) / (numExchange - 1). Add this value to the initial bottles to get the final answer. This relies on a small piece of math reasoning that compresses the entire simulation into constant time.

The mathematical solution runs in O(1) time and O(1) space because it performs only a few arithmetic operations. It is elegant and optimal once you recognize the invariant created by the exchange rule.

Recommended for interviews: Start with the iterative simulation because it clearly demonstrates understanding of the exchange mechanics and uses straightforward logic. After that, mention the mathematical shortcut as an optimization. Interviewers often appreciate candidates who first build the correct simulation and then derive the O(1) formula from the observation that each extra drink effectively costs numExchange - 1 empties.