
Intuition
The problem requires determining the maximum number of water bottles that can be consumed, considering the ability to exchange empty bottles for full ones. Initially, you have a certain number of full water bottles (numBottles
). Each time you drink a bottle, it turns into an empty bottle, and once you accumulate enough empty bottles (numExchange
), you can trade them for a new full bottle.
The intuition is to continuously keep track of the number of full and empty bottles, ensuring to maximize the drinking process by always exchanging empty bottles for full ones when possible.
Approach
- Initial Setup: Start with the given number of full bottles (
numBottles
). - Drink and Exchange: Implement a loop where, in each iteration, you: - Drink all the current full bottles, adding to the total count of bottles drunk. - Convert all these full bottles into empty bottles. - Exchange as many empty bottles as possible for new full bottles. - Keep any remaining empty bottles that couldn't be exchanged.
- Repeat: Continue this process until no more exchanges can be made (i.e., when the number of empty bottles is less than
numExchange
). - Terminate: Return the total count of bottles drunk as the result.
In terms of implementation, we can use a while loop to simulate this process, updating the count of full and empty bottles at each step.
Formula Derivation
To derive the formula numBottles + (numBottles - 1) // (numExchange - 1)
, let's break down the process and understand how it accounts for the maximum number of water bottles you can drink:
Step-by-Step Explanation
- Initial Full Bottles: Start with
numBottles
full bottles. - Drinking and Exchanging:
- For each bottle you drink, you get one empty bottle.
- You can exchange
numExchange
empty bottles for one full bottle. - Counting Bottles:
- Initially, you can drink
numBottles
full bottles. - After drinking, you will havenumBottles
empty bottles. - To determine how many additional full bottles you can get from exchanges, note that for everynumExchange
empty bottles, you get one full bottle.
Simplified Calculation
Instead of simulating the process, observe the relationship between the number of bottles and exchanges:
- Total Bottles Drunk:
- Let's denote the total number of bottles you can drink by
T
. - Exchanges Needed:
- Each exchange gives one full bottle for
numExchange
empty bottles. - After each exchange, the number of empty bottles reduces and needs to be recalculated. - Formula Derivation:
- The key insight is to recognize a pattern in the exchanges. Specifically, each exchange reduces the total count of bottles by
numExchange - 1
(because one bottle is gained whilenumExchange
empty bottles are used up). - Therefore, the total number of bottles drunk, considering initial bottles and exchanges, can be calculated directly without iterating.
General Formula
Combining these insights, the total number of bottles drunk can be expressed as:
\[ T = numBottles + floor((numbottles - 1) / (numExchange - 1)) \]
Explanation of the Formula
numBottles
: Represents the initial count of full bottles.(numBottles - 1) // (numExchange - 1)
: Represents the total number of additional bottles you can get through exchanges. Subtracting 1 fromnumBottles
andnumExchange
aligns the exchange process with the available empty bottles.
By deriving this formula, we avoid the iterative process and directly calculate the maximum number of bottles that can be drunk.
Complexity
- Time Complexity: \(O(1)\) - The formula allows us to compute the result in constant time without needing iteration.
- Space Complexity: \(O(1)\) - The approach uses a constant amount of additional space regardless of the input size.
Code
C++
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
return numBottles + (numBottles - 1) / (numExchange - 1);
}
};
Python
Java
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
return numBottles + (numBottles - 1) / (numExchange - 1);
}
}
JavaScript
/**
* @param {number} numBottles
* @param {number} numExchange
* @return {number}
*/
var numWaterBottles = function(numBottles, numExchange) {
return numBottles + Math.floor((numBottles-1)/(numExchange-1));
};