Get started

Water Bottles II — Medium Problem & Solution

You have numBottles full water bottles. Drinking one turns it into an empty bottle.

  • Difficulty: Medium
  • Topics: Math, Simulation
  • Asked at: Amazon, Google, Zoho
  • 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. Drinking one turns it into an empty bottle.

You may hand over numExchange empty bottles for one full bottle — and each time you do, numExchange increases by one. Return the maximum number of bottles you can drink.

Example 1

Input: numBottles = 13, numExchange = 6
Output: 15
Explanation: Two exchanges are possible before the empties run short.

Example 2

Input: numBottles = 10, numExchange = 3
Output: 13
Explanation: Three exchanges, at costs 3, 4 and 5.

Example 3

Input: numBottles = 1, numExchange = 2
Output: 1
Explanation: Never enough empties to trade.

Constraints

  • 1 <= numBottles <= 100
  • 1 <= numExchange <= 100

How to solve Water Bottles II

Simulate. Drink the initial bottles, then keep exchanging while you have enough empties, remembering that the price rises by one after each trade and that the bottle you win becomes another empty.

Approach

  1. Start drunk and empty at numBottles.
  2. While empty >= numExchange: pay the empties, raise the price, drink the new bottle and add its empty back.
  3. Return drunk.

Why it works

The rising price is what bounds the loop: the total spend grows quadratically, so with at most 100 bottles only a handful of trades are ever possible. Forgetting to add the new empty back under-counts, since the bottle you drink is still a bottle afterwards.

Complexity

  • Time — O(√numBottles)
  • Space — O(1)

Pitfalls

  • The exchanged bottle becomes an empty once drunk and can fund a later trade.
  • The price increases after each exchange, not before the first.
  • A fixed price would be the original Water Bottles problem, which has a closed form.

Reference solution

Python

def maxBottlesDrunk(numBottles: int, numExchange: int) -> int:
    drunk = numBottles
    empty = numBottles
    ex = numExchange
    while empty >= ex:
        empty -= ex
        ex += 1
        drunk += 1
        empty += 1
    return drunk

JavaScript

var maxBottlesDrunk = function(numBottles, numExchange) {
    var drunk = numBottles;
    var empty = numBottles;
    var ex = numExchange;
    while (empty >= ex) {
        empty -= ex;
        ex++;
        drunk++;
        empty++;
    }
    return drunk;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue