Water Bottles II - Practice Coding Problems

Water Bottles II - Problem

Math Simulation Medium

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: 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.

Input & Output

Example 1 — Basic Case

$ Input: numBottles = 13, numExchange = 6

› Output: 15

💡 Note: Drink 13 bottles → 13 empties. Exchange 6 empties for 1 new bottle (cost becomes 7), leaving 7+1=8 empties. Drink 1 bottle → 8 empties. Exchange 7 empties for 1 new bottle (cost becomes 8), leaving 1+1=2 empties. Drink 1 bottle → 2 empties. Cannot exchange anymore (need 8, have 2). Total: 13+1+1=15

Example 2 — Higher Exchange Cost

$ Input: numBottles = 10, numExchange = 3

› Output: 13

💡 Note: Drink 10 → 10 empties. Exchange 9 for 3 (cost=3), 1 empty left + 3 new = 4 empties total. Drink 3 → 7 empties. Exchange 4 for 1 (cost=4), 3 left + 1 new = 4 empties. Drink 1 → 5 empties. Exchange 5 for 1 (cost=5), 0 left + 1 new = 1 empty. Drink 1 → 1 empty. Total: 10+3+1+1=15

Example 3 — No Exchanges Possible

$ Input: numBottles = 2, numExchange = 4

› Output: 2

💡 Note: Drink 2 bottles → 2 empties. Cannot exchange (need 4, have 2). Total: 2

Constraints

1 ≤ numBottles ≤ 100
1 ≤ numExchange ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

numBottles=13 initial bottles, numExchange=6 exchange rate

Process

Drink bottles, exchange empties with increasing cost

Output

Total bottles drunk = 15

Key Takeaway

🎯 Key Insight: The exchange cost increases after each round, making fewer exchanges possible over time

Asked in

G Google 15 a Amazon 12

The key insight is to simulate the exchange process where each exchange increases the cost. We drink initial bottles, then repeatedly exchange empty bottles for new ones until impossible. Best approach uses mathematical calculation to avoid separate drinking/exchanging loops. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Approach	O(log n)	O(1)	Calculate exchanges mathematically without explicit simulation
Simulation	O(log n)	O(1)	Simulate the drinking and exchanging process step by step

Mathematical Approach — Algorithm Steps

Step 1: Start with initial bottles as both drunk count and empty bottles
Step 2: For each exchange rate, calculate maximum exchanges possible
Step 3: Update empty bottles and total drunk, increment exchange rate
Step 4: Continue until no more exchanges are possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set totalDrunk and emptyBottles to initial bottles

Calculate

For each rate, compute exchanges in one step

Update

Add exchanged bottles to total and update empties

Code -

solution.c — C

#include <stdio.h>

int solution(int numBottles, int numExchange) {
    int totalDrunk = numBottles;
    int emptyBottles = numBottles;
    
    while (emptyBottles >= numExchange) {
        int exchangeCount = emptyBottles / numExchange;
        emptyBottles = emptyBottles % numExchange + exchangeCount;
        totalDrunk += exchangeCount;
        numExchange++;
    }
    
    return totalDrunk;
}

int main() {
    int numBottles, numExchange;
    scanf("%d", &numBottles);
    scanf("%d", &numExchange);
    
    int result = solution(numBottles, numExchange);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Each exchange rate processes fewer bottles, leading to logarithmic total iterations

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for calculations

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler