Water Bottles: Simulation and Math

LeetCode 1518. Water Bottles gives you numBottles full water bottles and a number numExchange, the number of empty bottles you need to trade in for one new full bottle. You drink all your full bottles (turning them into empties), exchange as many empties as you can for new full bottles, drink those, and repeat until you can no longer exchange. Return the total number of bottles you drank.

The simulation approach

The most natural way to solve this is to simulate the process directly. You keep a running total of bottles drunk and a count of empty bottles on hand. Each round you drink all full bottles, add them to the empty pile, then exchange as many empties as possible for new full bottles (using integer division). The remainder stays in your empty pile for the next round.

def num_water_bottles(num_bottles: int, num_exchange: int) -> int:
    total = 0
    empty = 0
    full = num_bottles

    while full > 0:
        total += full
        empty += full
        full = empty // num_exchange
        empty = empty % num_exchange

    return total

This loop runs until you have zero full bottles, meaning you cannot exchange anymore. Each iteration handles one round of drinking and exchanging.

Step-by-step walkthrough: numBottles = 9, numExchange = 3

Let's trace through the simulation to see every round of drinking and exchanging.

Three rounds and we are done. The total is 13 bottles drunk from an initial supply of just 9.

The math shortcut

There is also a closed-form solution. Every time you exchange numExchange empties for 1 full bottle, you are effectively "using up" numExchange - 1 empties (because drinking that new bottle gives 1 empty back). So each exchange consumes a net of numExchange - 1 empties.

You start with numBottles empties (after drinking all of them). The number of additional bottles you can gain is (numBottles - 1) // (numExchange - 1). Add that to the original numBottles and you have the answer.

def num_water_bottles(num_bottles: int, num_exchange: int) -> int:
    return num_bottles + (num_bottles - 1) // (num_exchange - 1)

Why numBottles - 1 instead of numBottles? Because the last empty bottle cannot be exchanged on its own. The floor division naturally handles this: it counts how many complete exchanges you can make from all the empties that flow through the system.

Complexity analysis

The simulation loop runs once per exchange round. Each round reduces the number of full bottles by a factor of roughly numExchange, so the number of iterations is O(log n) where n is numBottles. The math formula computes the answer in constant time with a single division.

Building blocks

This problem breaks down into two reusable ideas you will see in other problems.

1. Simulate until a condition fails

The core loop pattern is: do something, update state, check if you can continue. This is the same structure used in any greedy simulation, from making change to processing queues. The key is identifying what state to track (full and empty counts) and what the termination condition is (no more full bottles).

while can_continue:
    process(state)
    state = update(state)

2. Integer division for grouping

Using // and % to split a count into "complete groups" and "remainder" is one of the most common micro-patterns in algorithm problems. Here it splits empties into exchangeable groups and leftover bottles. You see the same pattern in problems involving pages, batches, rows, and any scenario where items are consumed in fixed-size groups.

groups = total // group_size
remainder = total % group_size

Edge cases

• numExchange = 2: Maximum bonus bottles. Every 2 empties becomes 1 full, so you nearly double your initial count. For numBottles = 9, the answer is 17.
• numBottles = 1: You drink 1 bottle and have 1 empty. If numExchange is greater than 1, you cannot exchange. The answer is 1.
• numExchange greater than numBottles: You drink all bottles but never have enough empties to exchange even once. The answer is just numBottles.
• Large numExchange: As numExchange grows, the bonus from exchanging shrinks. In the limit, the answer approaches numBottles itself.

From understanding to recall

Water Bottles is a simple problem, but the simulation loop pattern and the integer division grouping trick appear everywhere. Being able to write them quickly and correctly under pressure matters more than understanding them in the abstract.

That is what spaced repetition solves. CodeBricks breaks this problem into its two building blocks and drills them at increasing intervals. You type each piece from scratch, not from memorizing the full solution, but from understanding the pattern. After a few review cycles, "simulate until done" and "divide into groups with remainder" become automatic.

Related posts

• Happy Number - Another simulation loop that runs until a condition is met (reaching 1 or detecting a cycle), the same "loop until done" structure used here
• Power of Two - A math-based problem where recognizing a numeric property gives you a one-liner, similar to how the math formula here replaces the simulation
• Fizz Buzz - Uses modular arithmetic and integer division to classify numbers, the same // and % building blocks that power the exchange logic