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.
Solutions
Solution
class Solution {public int numWaterBottles(int numBottles, int numExchange) { int ans = numBottles; for (; numBottles >= numExchange; ++ans) { numBottles -= (numExchange - 1); } return ans; }}Video 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.