0583EasyMathSimulation

Canteen Refills on the Ridge

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A ridge depot keeps hikers supplied with drinking water. You set out holding numBottles sealed bottles.

Emptying a sealed bottle leaves you with one used container, and you always keep your used containers. The depot will hand over one fresh sealed bottle in return for numExchange used containers, and you may go back to the counter as often as you like while you still hold that many used containers.

Return how many bottles you empty in total.

Examples

Example 1

Input: numBottles = 12, numExchange = 4
Output: 15

Emptying the 12 sealed bottles leaves 12 containers, which trade for 3 sealed bottles. Emptying those brings the tally to 15 and leaves 3 containers, too few for another trade.

Example 2

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

Six containers never reach the 100 the counter asks for, so the only bottles emptied are the six carried in.

Example 3

Input: numBottles = 100, numExchange = 2
Output: 199

Trips to the counter bring back 50, then 25, then 12 with one container held over, then 6, 3, 2 and 1, and the tally reaches 199.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_water_bottles(numBottles: int, numExchange: int) -> int:

Java

public int numWaterBottles(int numBottles, int numExchange)

The intended approach

Time O(1) — one division.Space O(1).

Follow a single trade through: `numExchange` used containers leave your hands and one sealed bottle comes back, which you then empty, returning one container. So a trade shrinks the container pile by `numExchange - 1` and adds exactly one bottle to the tally. Trading stops once fewer than `numExchange` containers remain, which fixes the number of trades by integer division and gives the answer in constant time.

Pythonentry point: num_water_bottles

def num_water_bottles(numBottles, numExchange):
    # O(1) time, O(1) space: each trade turns numExchange empties into one
    # sealed bottle, which is emptied in turn, so every trade costs a net
    # numExchange - 1 containers out of the pile. Trading continues while at
    # least numExchange empties remain, which caps the number of trades.
    return numBottles + (numBottles - 1) // (numExchange - 1)

The obvious version

Step through the trips to the counter. Empty every sealed bottle in hand, add those containers to the pile, trade as many full groups as the pile allows, carry the remainder forward, and repeat until a trip brings back nothing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_water_bottles(numBottles, numExchange):
    sealed = numBottles
    empty = 0
    drunk = 0
    while sealed > 0:
        drunk += sealed
        empty += sealed
        sealed = empty // numExchange
        empty = empty % numExchange
    return drunk

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in