numBottles full water bottles, you can exchange
numExchange empty water bottles for one full water bottle.
The operation of drinking a full water bottle turns it into an empty bottle.
Return the maximum number of water bottles you can drink.
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.
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.
Input: numBottles = 5, numExchange = 5 Output: 6
Input: numBottles = 2, numExchange = 3 Output: 2
1 <= numBottles <= 100
2 <= numExchange <= 100
The key idea is to simulate the process, find out what are the steps in one iteration and what’s the condition to loop the iteration. Base on the example picture, we can consider 1. drinking bottles to empty bottles 2. exchange empty bottles for new bottles as steps in one iteration. Then when bottles + empty bottles are greater than the minimum exchange number, we loop the process.
class Solution: def numWaterBottles(self, numBottles: int, numExchange: int) -> int: count = 0 empty_bottles = 0 while numBottles + empty_bottles >= numExchange: count += numBottles empty_bottles += numBottles numBottles = empty_bottles // numExchange empty_bottles = empty_bottles % numExchange count += numBottles return count
- Time Complexity: O(N).
- Space Complexity: O(1).