LeetCode 1518. Water Bottles Java Solution
Problem Description
Problem: LeetCode 1518. Water Bottles
Description: We have
numBottles
water bottles. We can exchangenumExchange
empty bottles for one new full water bottle. The goal is to calculate the maximum number of water bottles we can drink.
Approach
Idea:
Initially, we drink all
numBottles
water bottles.After drinking, we have
numBottles
empty bottles.We exchange the empty bottles for new full bottles as much as possible. We drink these new bottles and repeat the process until we can't exchange anymore.
We repeat this process until the number of empty bottles is less than
numExchange
.Finally, we return the total number of water bottles we can drink.
Algorithm:
Initialize
canDrink
with the initial number of water bottles.While
numBottles
is greater than or equal tonumExchange
:Calculate the number of new bottles obtained by dividing
numBottles
bynumExchange
. (numBottles / numExchange)As
newBottles
is of type int, any fractional part is discarded.Calculate the remaining empty bottles after exchanging, which is
numBottles
modulonumExchange
. (numBottles % numExchange)Add the number of new bottles to
canDrink
.Update
numBottles
to the sum of the new bottles obtained and the remaining empty bottles.
After the loop ends, return the value of
canDrink
.
Code
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int canDrink = numBottles;
while(numBottles >= numExchange){
int newBottles = numBottles / numExchange;
canDrink += newBottles;
numBottles = newBottles + (numBottles % numExchange);
}
return canDrink;
}
}
Conclusion
Time Complexity:
The number of bottles decreases with each exchange, so the loop runs at most
log(numBottles)
times.Thus, the time complexity is O(log n).
Space Complexity:
- No additional space is used, so the space complexity is O(1).