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.
Example 1:
Input: numBottles = 9, numExchange = 3 Output: 13 Explanation: You can exchange 3 empty bottles to get 1 full water bottle. Number of water bottles you can drink: 9 + 3 + 1 = 13.
Example 2:
Input: numBottles = 15, numExchange = 4 Output: 19 Explanation: You can exchange 4 empty bottles to get 1 full water bottle. Number of water bottles you can drink: 15 + 3 + 1 = 19.
Constraints:
1 <= numBottles <= 1002 <= numExchange <= 100Problem 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.
This approach uses a simple iterative simulation to solve the problem. We keep track of the current number of full bottles and empty bottles. We repeatedly drink a full bottle and calculate how many empty bottles we have. If the number of empty bottles is enough to exchange for a new full bottle, we perform the exchange and continue the loop. This process is repeated until no more exchanges can be made.
The function numWaterBottles calculates the maximum number of water bottles one can drink. It uses a loop to repeatedly simulate drinking and exchanging bottles while keeping track of total bottles drunk and current empty bottles.
Time Complexity: O(numBottles).
Space Complexity: O(1).
This approach leverages a mathematical understanding of the problem. Instead of simulating every exchange, you can calculate how many overall bottles you'll get by using a formula. This involves understanding the number of bottles resulting from continuous exchanges until no more can be made.
In this C solution, a while loop is used to calculate the total number of bottles drunk by updating the current bottles with the new one obtained from the exchange.
Time Complexity: O(log(numBottles)).
Space Complexity: O(1).
Python
Java
C++
Go
TypeScript
JavaScript
PHP
| Approach | Complexity |
|---|---|
| Iterative Simulation | Time Complexity: O(numBottles). |
| Mathematical Approach | Time Complexity: O(log(numBottles)). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(n) | O(1) | Best when explaining logic step‑by‑step or implementing the straightforward interpretation of the problem. |
| Mathematical Formula | O(1) | O(1) | Use when optimizing after recognizing the pattern that each extra drink effectively costs (numExchange − 1) empty bottles. |
LeetCode 1518 | Water Bottles | Day 5 | 100_Days_LeetCode_Challenge | Master DSA with edSlash • edSlash • 27,559 views views
Watch 9 more video solutions →Practice Water Bottles with our built-in code editor and test cases.
Practice on FleetCode