Water Bottles — Solution in Python, Java & C++
Water Bottles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.
Water Bottles is an easy coding problem on math and simulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Math, Simulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have numBottles full water bottles. You can trade numExchange empty bottles for one full bottle.
Drinking a full bottle turns it into an empty one. Return the maximum number of bottles you can drink.
Example 1
Input: numBottles = 9, numExchange = 3
Output: 13
Example 2
Input: numBottles = 15, numExchange = 4
Output: 19
Example 3
Input: numBottles = 5, numExchange = 5
Output: 6
Constraints
1 <= numBottles <= 1000002 <= numExchange <= 100
Hints for Water Bottles
Hint 1
Track two numbers: how many you have drunk, and how many empties you hold.
Hint 2
Each exchange converts
numExchangeempties into one full bottle — which becomes one more empty after you drink it.Hint 3
Loop while you still hold enough empties to trade.
How to solve Water Bottles
Track bottles drunk and empties held; each exchange turns numExchange empties into one full bottle, which becomes one more empty.
Approach
- Start
drunk = empty = numBottles. - While
empty >= numExchange:fresh = empty // numExchange; addfreshtodrunk;empty = empty - fresh · numExchange + fresh.
Why it works
Exchanging as soon as possible is optimal because bottles are fungible; the loop terminates because each round strictly reduces the empties.
Complexity
- Time —
O(log numBottles) - Space —
O(1)
Pitfalls
- The closed form
numBottles + (numBottles - 1) // (numExchange - 1)is equivalent.
Reference solution
Python
def numWaterBottles(numBottles: int, numExchange: int) -> int:
drunk = numBottles
empty = numBottles
while empty >= numExchange:
fresh = empty // numExchange
drunk += fresh
empty = empty - fresh * numExchange + fresh
return drunkJava
public static int numWaterBottles(int numBottles, int numExchange) {
int drunk = numBottles, empty = numBottles;
while (empty >= numExchange) {
int fresh = empty / numExchange;
drunk += fresh;
empty = empty - fresh * numExchange + fresh;
}
return drunk;
}C++
int numWaterBottles(int numBottles, int numExchange) {
int drunk = numBottles, empty = numBottles;
while (empty >= numExchange) {
int fresh = empty / numExchange;
drunk += fresh;
empty = empty - fresh * numExchange + fresh;
}
return drunk;
}JavaScript
var numWaterBottles = function(numBottles, numExchange) {
let drunk = numBottles;
let empty = numBottles;
while (empty >= numExchange) {
const fresh = Math.floor(empty / numExchange);
drunk += fresh;
empty = empty - fresh * numExchange + fresh;
}
return drunk;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.