Water Bottles
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 <= 100
- 2 <= numExchange <= 100
Approach 1: 循环
class Solution {
fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
var ans = numBottles
var empty = numBottles
while (empty >= numExchange) {
val exchange = empty / numExchange
ans += exchange
empty = exchange + empty % numExchange
}
return ans
}
}
Approach 2: 递归
class Solution {
fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
val d = numBottles.div(numExchange)
val m = numBottles.mod(numExchange)
if (d == 0) return numBottles
return d * numExchange + numWaterBottles(d + m, numExchange)
}
}
Approach 3: 奇技淫巧
让我们设想如下场景：如果你有 (numExchange-1) 个空瓶，你可以从朋友那里借一个满瓶，喝掉这瓶后你就有了 numExchange 个空瓶， 然后用这 numExchange 个空瓶兑换一个满瓶，并把它还给你朋友。你的朋友没有任何损失，而你多喝了一瓶。
现在回到这个问题，你有 numBottles 个满瓶，先取出一个让朋友保管，余下 (numBottles-1) 个满瓶，喝光得到了 (numBottles-1) 个空瓶，然后循环上面借瓶兑换的步骤，直到无法兑换，最后再把朋友保管的那瓶要回来喝光。
所以，我们可以算出通过兑换额外喝到的瓶子数量：(numBottles - 1)/(numExchange - 1)，再加上初始拥有的 numBottles 便是总和。
class Solution {
fun numWaterBottles(numBottles: Int, numExchange: Int): Int {
return numBottles + (numBottles - 1).div(numExchange - 1)
}
}