Water Bottles
Problem
You buy numBottles full water bottles. Every bottle you drink becomes an empty bottle, and the shop lets you swap exactly numExchange empties for one new full bottle. Trades can be repeated as long as you can afford them.
Return the maximum total number of bottles you can drink. Constraints: 1 ≤ numBottles ≤ 100 and 2 ≤ numExchange ≤ 100.
numBottles = 9, numExchange = 313def num_water_bottles(num_bottles, num_exchange):
total = num_bottles # drink every bottle we start with
empty = num_bottles # they all become empties
while empty >= num_exchange:
gained = empty // num_exchange
total += gained # drink the freshly traded bottles
empty = empty % num_exchange + gained
return totalfunction numWaterBottles(numBottles, numExchange) {
let total = numBottles; // drink every bottle we start with
let empty = numBottles; // they all become empties
while (empty >= numExchange) {
const gained = Math.floor(empty / numExchange);
total += gained; // drink the freshly traded bottles
empty = empty % numExchange + gained;
}
return total;
}int numWaterBottles(int numBottles, int numExchange) {
int total = numBottles; // drink every bottle we start with
int empty = numBottles; // they all become empties
while (empty >= numExchange) {
int gained = empty / numExchange;
total += gained; // drink the freshly traded bottles
empty = empty % numExchange + gained;
}
return total;
}int numWaterBottles(int numBottles, int numExchange) {
int total = numBottles; // drink every bottle we start with
int empty = numBottles; // they all become empties
while (empty >= numExchange) {
int gained = empty / numExchange;
total += gained; // drink the freshly traded bottles
empty = empty % numExchange + gained;
}
return total;
}Explanation
This is a greedy simulation. Drinking a bottle never hurts you — it is the only way to score and it produces an empty that may later be traded — so the best strategy is simply: drink everything you have, then trade empties for new bottles whenever you can afford to.
We keep two counters. total is the number of bottles drunk so far, and empty is how many empties are currently in hand. Both start at numBottles, because we immediately drink the whole initial stock.
Each loop iteration is one trip to the shop: we trade as many complete groups of numExchange empties as possible, gaining gained = empty // numExchange full bottles. We drink those at once (total += gained), and the new empty count is the leftover that could not be traded plus the bottles we just drank: empty = empty % numExchange + gained. The loop stops when fewer than numExchange empties remain.
For the default example, numBottles = 9, numExchange = 3: drink 9 (total 9, empties 9), trade 9 empties for 3 bottles and drink them (total 12, empties 3), trade those 3 for 1 bottle and drink it (total 13, empties 1). One empty is fewer than three, so the answer is 13.
Each iteration replaces empty with roughly empty / numExchange, so the count shrinks geometrically and the loop runs only about log(numBottles) times using constant extra space. (There is even a closed form — numBottles + (numBottles − 1) / (numExchange − 1) rounded down — but the simulation is just as fast in practice and far easier to trust.)