Water Bottles
EasyPrompt
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 <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of drinking bottles and exchanging empty ones for full ones. We use a loop that continues as long as we can obtain new bottles from exchanges. In each iteration, we calculate how many new bottles can be acquired, add them to our count of drinks, and update the number of empty bottles for the next round.
Algorithm
- Initialize
totalDrunktonumBottles. - Initialize
emptyBottlestonumBottles. - Loop as long as
emptyBottles >= numExchange:- Calculate
newBottles = emptyBottles / numExchange. - Increment
totalDrunkbynewBottles. - Update
emptyBottles = (emptyBottles % numExchange) + newBottles.
- Calculate
- Return
totalDrunk.
Walkthrough
We start by drinking all the initial numBottles. This sets our initial totalDrunk count and gives us numBottles empty bottles. Then, we enter a loop that continues as long as we have enough empty bottles to make an exchange (i.e., emptyBottles >= numExchange).
Inside the loop:
- We calculate how many new full bottles we can get by dividing the current number of
emptyBottlesbynumExchange. - We add this number of
newBottlesto ourtotalDrunkcount. - We update our count of
emptyBottles. The new count will be the sum of the bottles we just drank (newBottles) and any empty bottles that were left over from the exchange (emptyBottles % numExchange).
The loop terminates when we can no longer make any exchanges. The final totalDrunk is the result.
class Solution { public int numWaterBottles(int numBottles, int numExchange) { int totalDrunk = numBottles; int emptyBottles = numBottles; while (emptyBottles >= numExchange) { int newBottles = emptyBottles / numExchange; totalDrunk += newBottles; emptyBottles = (emptyBottles % numExchange) + newBottles; } return totalDrunk; }}Complexity
Time
O(log_{numExchange}(numBottles)). In each iteration, the number of empty bottles is roughly divided by `numExchange`. The number of iterations is therefore logarithmic with respect to the initial number of bottles.
Space
O(1). We only use a few variables to keep track of the counts, regardless of the input size.
Trade-offs
Pros
Intuitive and easy to understand as it directly models the problem statement.
Correct for all edge cases covered by the constraints.
Cons
Slightly less performant than a direct mathematical solution, although very fast for the given constraints.
A more advanced approach involves deriving a mathematical formula to solve the problem in constant time. By analyzing the net cost of empty bottles for each extra drink, we can find a direct relationship between the initial number of bottles and the total number of drinks.
Algorithm
- Calculate the number of extra bottles that can be obtained through exchanges using the formula:
extraBottles = (numBottles - 1) / (numExchange - 1). - The total number of drunk bottles is the sum of the initial bottles and the extra bottles:
totalDrunk = numBottles + extraBottles. - Return
totalDrunk.
Walkthrough
Let's analyze the exchange process from a different perspective. To obtain one new full bottle, we must trade numExchange empty bottles. After we drink this new bottle, it becomes an empty bottle itself. So, for every extra bottle we drink, we effectively reduce our total stock of empty bottles by numExchange - 1.
We start with numBottles full bottles. After drinking them, we have numBottles empty bottles. These are the 'currency' we can use for exchanges. The question becomes: how many times can we 'pay' the price of numExchange - 1 empty bottles when we start with numBottles empty bottles?
One might think the answer is numBottles / (numExchange - 1). However, we can't trade our very last empty bottle. The process must stop when we have fewer than numExchange bottles, and we can't get stuck with zero empty bottles and still be able to exchange. So, the total number of empty bottles we can afford to give up permanently is numBottles - 1.
The number of extra drinks (exchanges) we can get is (numBottles - 1) / (numExchange - 1).
Therefore, the total number of bottles we can drink is the initial numBottles plus these extra drinks.
Formula: totalDrunk = numBottles + (numBottles - 1) / (numExchange - 1)
This formula works even for edge cases. If numBottles < numExchange, then numBottles - 1 < numExchange - 1, and the integer division correctly results in 0 extra bottles.
class Solution { public int numWaterBottles(int numBottles, int numExchange) { // Each exchange for a new bottle costs `numExchange` empty bottles, // but we get one back after drinking it. The net cost is `numExchange - 1` empty bottles. // We start with `numBottles` empty bottles after drinking the initial set. // We can't use the very last empty bottle in an exchange, so we effectively have // `numBottles - 1` empty bottles to 'spend' on the net cost. // The number of extra bottles we can get is (numBottles - 1) / (numExchange - 1). if (numBottles < numExchange) { return numBottles; } return numBottles + (numBottles - 1) / (numExchange - 1); }}Complexity
Time
O(1). The solution involves a few arithmetic operations, which take constant time.
Space
O(1). No extra space is used that depends on the input size.
Trade-offs
Pros
Extremely efficient, providing a solution in constant time.
Elegant and concise.
Cons
The derivation of the formula is non-obvious and requires careful reasoning about the problem's mechanics.
Solutions
Solution
class Solution {public int numWaterBottles(int numBottles, int numExchange) { int ans = numBottles; for (; numBottles >= numExchange; ++ans) { numBottles -= (numExchange - 1); } return ans; }}/** * @param {number} numBottles * @param {number} numExchange * @return {number} */ var numWaterBottles = function ( numBottles , numExchange ) { let ans = numBottles ; for (; numBottles >= numExchange ; ++ ans ) { numBottles -= numExchange - 1 ; } return ans ; };class Solution {public: int numWaterBottles(int numBottles, int numExchange) { int ans = numBottles; for (; numBottles >= numExchange; ++ans) { numBottles -= (numExchange - 1); } return ans; }};class Solution: def numWaterBottles(self, numBottles: int, numExchange: int) -> int: ans = numBottles while numBottles >= numExchange: numBottles -= numExchange - 1 ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.