Water Bottles II

Medium
1000.

Water Bottles II

Water Bottles II is a medium coding problem on math and simulation, asked in Amazon, Google and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} numBottles
 * @param {number} numExchange
 * @return {number}
 */
var maxBottlesDrunk = function(numBottles, numExchange) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Water Bottles II — Solution in Python, Java & C++

Water Bottles II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and simulation.

Water Bottles II is a medium coding problem on math and simulation, asked in Amazon, Google and Zoho interviews.

  • 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

Hints for Water Bottles II

  1. Hint 1

    Drink everything first; every bottle drunk becomes an empty.

  2. Hint 2

    Each exchange costs the current numExchange empties and returns one full bottle — which becomes one more empty after drinking.

  3. Hint 3

    The cost rises every time, so the loop terminates quickly.

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

Java

public static int maxBottlesDrunk(int numBottles, int numExchange) {
    int drunk = numBottles;
    int empty = numBottles;
    int ex = numExchange;
    while (empty >= ex) {
        empty -= ex;
        ex++;
        drunk++;
        empty++;
    }
    return drunk;
}

C++

int maxBottlesDrunk(int numBottles, int numExchange) {
    int drunk = numBottles;
    int empty = numBottles;
    int ex = numExchange;
    while (empty >= ex) {
        empty -= ex;
        ex++;
        drunk++;
        empty++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue