1518. Water Bottles || LeetCode || C++
Solving LeetCode problem 1518. Water Bottles with a simple greedy approach in C++.
Intuition
We are given a number of full bottles and a rule that allows exchanging empty bottles for new full ones.
At first glance, this is similar to repeatedly trading resources:
every time we have enough empty bottles, we can exchange them for more full bottles.
The total number of bottles consumed will be the sum of:
- Initially available bottles
- Plus all future bottles obtained by exchanges.
Approach
- Start with
numBottlesfull bottles, so the total consumed begins atnumBottles. - After drinking them, we gain the same number of empty bottles.
- While the number of empty bottles is greater than or equal to
numExchange:- Exchange as many as possible:
t = numBottles / numExchange(new bottles obtained). - Add
tto the total consumed count. - Compute the remaining bottles after exchange:
rem = numBottles % numExchange. - The new count of empty bottles becomes
t + rem.
- Exchange as many as possible:
- Repeat until exchanges are no longer possible.
- Return the total consumed.
This greedy approach works because each exchange step maximizes the number of bottles we can drink at that stage.
Complexity
Time complexity:
Each loop iteration reduces the number of bottles by at least 1, so the loop runs at mostO(numBottles)times.
Effectively, the complexity is closer toO(log(numBottles))since bottles shrink quickly with division.Space complexity:
We only use a few extra variables (t,rem,numOfBottles), so the space usage isO(1).
Code (C++)
cpp
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
int numOfBottles = numBottles;
while (numBottles >= numExchange) {
int t = numBottles / numExchange; // number of new bottles obtained
int rem = numBottles % numExchange; // leftover bottles
numOfBottles += t;
numBottles = t + rem; // update for next round
}
return numOfBottles;
}
};
Top comments (0)