1518. Water Bottles

Problem

Given 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.

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.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

Problem Summary

The convenience store in the neighborhood is running a promotion: you can exchange numExchange empty bottles for one new bottle of wine. You bought numBottles bottles of wine.

If you drink the wine in a bottle, the bottle becomes empty.

Please calculate the maximum number of bottles of wine you can drink.

Solution Ideas

• Simulation. First, we can definitely drink numBottles bottles of wine, leaving numBottles empty bottles. Next, we can exchange empty bottles for wine: each time, take numExchange bottles to exchange for one bottle of wine, then drink this bottle and get one empty bottle. Simulate this process until the number of all empty bottles is less than numExchange.

Code

package leetcode

func numWaterBottles(numBottles int, numExchange int) int {
	if numBottles < numExchange {
		return numBottles
	}
	quotient := numBottles / numExchange
	reminder := numBottles % numExchange
	ans := numBottles + quotient
	for quotient+reminder >= numExchange {
		quotient, reminder = (quotient+reminder)/numExchange, (quotient+reminder)%numExchange
		ans += quotient
	}
	return ans
}