Water Bottles II

Problem

You are given two integers numBottles and numExchange.

numBottles represents the number of full water bottles that you initially have. In one operation, you can perform one of the following operations:

• Drink any number of full water bottles turning them into empty bottles.
• Exchange numExchange empty bottles with one full water bottle. Then, increase numExchange by one.

Note that you cannot exchange multiple batches of empty bottles for the same value of numExchange. For example, if numBottles == 3 and numExchange == 1, you cannot exchange 3 empty water bottles for 3 full bottles.

Return the maximum number of water bottles you can drink.

Examples

Example 1

	Full Bottles	Empty Bottles	numExchange	Bottles Drunk
Initially	13	0	6	0
Drink 13 bottles	0	13	6	13
Exchange	1	7	7	13
Exchange	2		8	13
Drink 2 bottles	0	2	8	15

Input: numBottles = 13, numExchange = 6
Output: 15
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Example 2

	Full Bottles	Empty Bottles	numExchange	Bottles Drunk
Initially	10	0	3	0
Drink 10 bottles	0	10	3	10
Exchange	1	7	4	10
Exchange	2	3	5	10
Drink 2 bottles	0	5	5	12
Exchange	1	0	6	12
Drink 1 bottle	0	1	6	13

Input: numBottles = 10, numExchange = 3
Output: 13
Explanation: The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

Constraints

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

Solution

Method 1 – Simulation

Intuition

Simulate the process: drink all full bottles, collect empty bottles, and exchange when possible. After each exchange, the number of empty bottles required increases by 1. Repeat until no more exchanges are possible.

Approach

Track the number of full and empty bottles. While you have enough empty bottles to exchange, perform the exchange, increment the total drunk, and update the exchange requirement. Stop when you can't exchange anymore.

Code

Python

class Solution:
    def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:
        total = numBottles
        empty = numBottles
        while empty >= numExchange:
            empty -= numExchange
            total += 1
            empty += 1
            numExchange += 1
        return total

Java

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        int total = numBottles, empty = numBottles;
        while (empty >= numExchange) {
            empty -= numExchange;
            total++;
            empty++;
            numExchange++;
        }
        return total;
    }
}

C++

class Solution {
public:
    int maxBottlesDrunk(int numBottles, int numExchange) {
        int total = numBottles, empty = numBottles;
        while (empty >= numExchange) {
            empty -= numExchange;
            total++;
            empty++;
            numExchange++;
        }
        return total;
    }
};

Go

func maxBottlesDrunk(numBottles int, numExchange int) int {
    total, empty := numBottles, numBottles
    for empty >= numExchange {
        empty -= numExchange
        total++
        empty++
        numExchange++
    }
    return total
}

Kotlin

class Solution {
    fun maxBottlesDrunk(numBottles: Int, numExchange: Int): Int {
        var total = numBottles
        var empty = numBottles
        var exchange = numExchange
        while (empty >= exchange) {
            empty -= exchange
            total++
            empty++
            exchange++
        }
        return total
    }
}

Rust

impl Solution {
    pub fn max_bottles_drunk(num_bottles: i32, num_exchange: i32) -> i32 {
        let (mut total, mut empty, mut exchange) = (num_bottles, num_bottles, num_exchange);
        while empty >= exchange {
            empty -= exchange;
            total += 1;
            empty += 1;
            exchange += 1;
        }
        total
    }
}

TypeScript

function maxBottlesDrunk(numBottles: number, numExchange: number): number {
    let total = numBottles, empty = numBottles;
    while (empty >= numExchange) {
        empty -= numExchange;
        total++;
        empty++;
        numExchange++;
    }
    return total;
}

Complexity

• ⏰ Time complexity: O(numBottles + numExchange) — Each exchange increases the requirement, so the loop runs at most numBottles + numExchange times.
• 🧺 Space complexity: O(1) — Only a few variables are used.