Water Bottles

Easy
440.

Water Bottles

Water Bottles is an easy coding problem on math and simulation, asked in Amazon and Adobe interviews.

You have numBottles full water bottles. You can trade numExchange empty bottles for one full bottle.

Drinking a full bottle turns it into an empty one. Return the maximum number of bottles you can drink.

Example 1

Input
numBottles = 9, numExchange = 3
Output
13

Example 2

Input
numBottles = 15, numExchange = 4
Output
19

Example 3

Input
numBottles = 5, numExchange = 5
Output
6

Constraints

  • 1 <= numBottles <= 100000
  • 2 <= 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 numWaterBottles = function(numBottles, numExchange) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Water Bottles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.

Water Bottles is an easy coding problem on math and simulation, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Math, Simulation
  • Asked at: Amazon, Adobe
  • 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. You can trade numExchange empty bottles for one full bottle.

Drinking a full bottle turns it into an empty one. Return the maximum number of bottles you can drink.

Example 1

Input: numBottles = 9, numExchange = 3
Output: 13

Example 2

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

Example 3

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

Constraints

  • 1 <= numBottles <= 100000
  • 2 <= numExchange <= 100

Hints for Water Bottles

  1. Hint 1

    Track two numbers: how many you have drunk, and how many empties you hold.

  2. Hint 2

    Each exchange converts numExchange empties into one full bottle — which becomes one more empty after you drink it.

  3. Hint 3

    Loop while you still hold enough empties to trade.

How to solve Water Bottles

Track bottles drunk and empties held; each exchange turns numExchange empties into one full bottle, which becomes one more empty.

Approach

  1. Start drunk = empty = numBottles.
  2. While empty >= numExchange: fresh = empty // numExchange; add fresh to drunk; empty = empty - fresh · numExchange + fresh.

Why it works

Exchanging as soon as possible is optimal because bottles are fungible; the loop terminates because each round strictly reduces the empties.

Complexity

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

Pitfalls

  • The closed form numBottles + (numBottles - 1) // (numExchange - 1) is equivalent.

Reference solution

Python

def numWaterBottles(numBottles: int, numExchange: int) -> int:
    drunk = numBottles
    empty = numBottles
    while empty >= numExchange:
        fresh = empty // numExchange
        drunk += fresh
        empty = empty - fresh * numExchange + fresh
    return drunk

Java

public static int numWaterBottles(int numBottles, int numExchange) {
    int drunk = numBottles, empty = numBottles;
    while (empty >= numExchange) {
        int fresh = empty / numExchange;
        drunk += fresh;
        empty = empty - fresh * numExchange + fresh;
    }
    return drunk;
}

C++

int numWaterBottles(int numBottles, int numExchange) {
    int drunk = numBottles, empty = numBottles;
    while (empty >= numExchange) {
        int fresh = empty / numExchange;
        drunk += fresh;
        empty = empty - fresh * numExchange + fresh;
    }
    return drunk;
}

JavaScript

var numWaterBottles = function(numBottles, numExchange) {
    let drunk = numBottles;
    let empty = numBottles;
    while (empty >= numExchange) {
        const fresh = Math.floor(empty / numExchange);
        drunk += fresh;
        empty = empty - fresh * numExchange + fresh;
    }
    return drunk;
};

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

All 337 math problems · the whole catalogue