Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Water Bottles II solution and explanation

MediumMathSimulation6 min read78.2% acceptanceUpdated 9 Apr 2026
Asked atGoogleAmazonMeta
Practise Water Bottles II
21:39
Water Bottles II | 2 Approaches | Sridharacharya formula | Leetcode 3100 | codestorywithMIKcodestorywithMIK · 21:39 · 4K viewsWatch on YouTube
9 more videos on this problem
  1. Water Bottles II | 2 Approaches | Sridharacharya formula | Leetcode 3100 | codestorywithMIKcodestorywithMIK · 21:39 · 4K views
  2. 3100. Water Bottles II | Simulation | Array | Weekly Contest 391Aryan Mittal · 10:05 · 3K views
  3. Water Bottles II | LeetCode 3100 | Complete Intuition ExplainedSanyam IIT Guwahati · 7:30 · 908 views
  4. 3100. Water Bottles II | Leetcode Daily - PythonLeetcode Daily · 7:09 · 894 views
  5. Daily Leetcode #2011: Oct 02, 2025 - 3100. Water Bottles IIProgramming Live with Larry · 6:11 · 638 views
  6. 3100. Water Bottles II (Leetcode Medium)Programming Live with Larry · 6:06 · 293 views
  7. Leetcode 3100: Water Bottles IIAlgorithms Casts · 10:20 · 216 views
  8. LeetCode 3100: Water Bottles II Explained – Easy Step-by-Step Solution || Java #ysabhishekmishraLogicDNA · 15:44 · 188 views
  9. 3100. Water Bottles II | SimulationTech Courses · 5:18 · 116 views
  10. 3100. Water Bottles II || Leetcode Weekly Contest 391Ashish Kumar · 4:39 · 78 views

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

Example 1:

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:

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

Approach overview

Problem Overview: You start with numBottles full bottles and can exchange empty bottles for a new full one. The catch: after every exchange, the number of empties required increases by 1. The task is to compute the maximum number of bottles you can drink.

Approach 1: Iterative Simulation (Time: O(k), Space: O(1))

This approach directly simulates the process described in the problem. Start by drinking all initial bottles, which gives you the same number of empty bottles. While the number of empty bottles is at least the current exchange requirement (numExchange), perform an exchange: spend the required empties, gain one full bottle, drink it, and increase the exchange cost by one. Each iteration represents a single exchange operation. The logic is simple and mirrors the rules exactly, making it easy to reason about and implement using basic simulation. Time complexity is O(k), where k is the number of exchanges performed, and space complexity is O(1).

The key insight is that every exchange consumes cost empty bottles but returns one new empty after drinking the obtained bottle. The net change in empties per exchange is therefore -(cost - 1). As the required exchange cost keeps increasing, the loop eventually terminates when there are not enough empty bottles left.

Approach 2: Mathematical Optimization (Time: O(1), Space: O(1))

The simulation can be replaced with a mathematical observation. Suppose you perform k exchanges. The exchange costs form an increasing sequence: numExchange, numExchange + 1, ..., numExchange + k - 1. The total number of empty bottles spent is the sum of this arithmetic progression. Each exchange also produces one new empty bottle after drinking the obtained bottle. Using math, the remaining empty bottles after k exchanges can be expressed as:

empties = numBottles - (numExchange + (numExchange+1) + ... + (numExchange+k-1)) + k

This simplifies to numBottles - (k * numExchange + k(k-1)/2) + k. The valid number of exchanges is the largest k such that before each step you still have enough empties to pay the required cost. Solving this inequality allows you to compute k directly using arithmetic progression formulas. The final answer becomes numBottles + k. This approach eliminates iteration entirely and relies on arithmetic reasoning, which is common in problems tagged with Math.

Recommended for interviews: The iterative simulation is usually expected first because it clearly follows the rules of the problem and is easy to verify. It demonstrates solid reasoning and careful state updates. The mathematical optimization is a strong follow‑up that shows deeper insight into arithmetic progressions and constraint analysis. In most interviews, presenting the simulation first and then deriving the constant‑time optimization shows both correctness and problem‑solving depth.

Approach 1: Iterative Simulation

This approach simulates the process of drinking water bottles and exchanging empty ones iteratively. We keep track of the number of full and empty bottles and perform exchanges as long as possible. In each iteration, all full bottles are consumed, and empty bottles are exchanged for new full bottles. Note that each time we perform an exchange, we increment the exchange rate by one, which affects the number of exchanges possible in future iterations.

def max_bottles(num_bottles, num_exchange):
    total_drunk = 0
    current_ex_rate = num_exchange
    while num_bottles > 0:
        total_drunk += num_bottles
        new_num_bottles = num_bottles // current_ex_rate
        num_bottles = new_num_bottles
        current_ex_rate += 1
    return total_drunk

# Example usage:
print(max_bottles(13, 6))  # Output: 15
print(max_bottles(10, 3))  # Output: 13
public class WaterBottles {
    public static int maxBottles(int numBottles, int numExchange) {
        int totalDrunk = 0;
        int currentExRate = numExchange;
        while (numBottles > 0) {
            totalDrunk += numBottles;
            int newNumBottles = numBottles / currentExRate;
            numBottles = newNumBottles;
            currentExRate++;
        }
        return totalDrunk;
    }

    public static void main(String[] args) {
        System.out.println(maxBottles(13, 6)); // Output: 15
        System.out.println(maxBottles(10, 3)); // Output: 13
    }
}
#include <iostream>

int maxBottles(int numBottles, int numExchange) {
    int totalDrunk = 0;
    int currentExRate = numExchange;
    while (numBottles > 0) {
        totalDrunk += numBottles;
        int newNumBottles = numBottles / currentExRate;
        numBottles = newNumBottles;
        currentExRate++;
    }
    return totalDrunk;
}

int main() {
    std::cout << maxBottles(13, 6) << std::endl; // Output: 15
    std::cout << maxBottles(10, 3) << std::endl; // Output: 13
    return 0;
}
function maxBottles(numBottles, numExchange) {
    let totalDrunk = 0;
    let currentExRate = numExchange;
    while (numBottles > 0) {
        totalDrunk += numBottles;
        let newNumBottles = Math.floor(numBottles / currentExRate);
        numBottles = newNumBottles;
        currentExRate++;
    }
    return totalDrunk;
}

console.log(maxBottles(13, 6)); // Output: 15
console.log(maxBottles(10, 3)); // Output: 13;
#include <stdio.h>

int maxBottles(int numBottles, int numExchange) {
    int totalDrunk = 0;
    int currentExRate = numExchange;
    while (numBottles > 0) {
        totalDrunk += numBottles;
        int newNumBottles = numBottles / currentExRate;
        numBottles = newNumBottles;
        currentExRate++;
    }
    return totalDrunk;
}

int main() {
    printf("%d\n", maxBottles(13, 6)); // Output: 15
    printf("%d\n", maxBottles(10, 3)); // Output: 13
    return 0;
}
using System;

public class WaterBottles {
    public static int MaxBottles(int numBottles, int numExchange) {
        int totalDrunk = 0;
        int currentExRate = numExchange;
        while (numBottles > 0) {
            totalDrunk += numBottles;
            int newNumBottles = numBottles / currentExRate;
            numBottles = newNumBottles;
            currentExRate++;
        }
        return totalDrunk;
    }

    public static void Main() {
        Console.WriteLine(MaxBottles(13, 6)); // Output: 15
        Console.WriteLine(MaxBottles(10, 3)); // Output: 13
    }
}

This Python code is a straightforward translation of the iterative process. It continuously drinks bottles and exchanges them until no more full bottles can be procured.

Complexity

Time Complexity: O(log(numBottles))
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Mathematical Optimization

This approach computes the total number of water bottles through a mathematical lens, given the initial bottle count and exchange rate. Instead of simulating each drink and exchange operation, it leverages mathematical calculation to determine the upper bound of bottles that can be consumed and exchanged within given rules and conditions.

def max_bottles(num_bottles, num_exchange):
    total_drunk = num_bottles
    empties = 0
    current_ex_rate = num_exchange
    while num_bottles > 0:
        empties += num_bottles
        new_bottles = empties // current_ex_rate
        empties = empties % current_ex_rate
        num_bottles = new_bottles
        total_drunk += new_bottles
        current_ex_rate += 1
    return total_drunk

# Example usage:
print(max_bottles(13, 6))  # Output: 15
print(max_bottles(10, 3))  # Output: 13
public class WaterBottles {
    public static int maxBottles(int numBottles, int numExchange) {
        int totalDrunk = numBottles;
        int empties = 0;
        int currentExRate = numExchange;
        while (numBottles > 0) {
            empties += numBottles;
            int newBottles = empties / currentExRate;
            empties = empties % currentExRate;
            numBottles = newBottles;
            totalDrunk += newBottles;
            currentExRate++;
        }
        return totalDrunk;
    }

    public static void main(String[] args) {
        System.out.println(maxBottles(13, 6)); // Output: 15
        System.out.println(maxBottles(10, 3)); // Output: 13
    }
}
#include <iostream>

int maxBottles(int numBottles, int numExchange) {
    int totalDrunk = numBottles;
    int empties = 0;
    int currentExRate = numExchange;
    while (numBottles > 0) {
        empties += numBottles;
        int newBottles = empties / currentExRate;
        empties = empties % currentExRate;
        numBottles = newBottles;
        totalDrunk += newBottles;
        currentExRate++;
    }
    return totalDrunk;
}

int main() {
    std::cout << maxBottles(13, 6) << std::endl; // Output: 15
    std::cout << maxBottles(10, 3) << std::endl; // Output: 13
    return 0;
}
function maxBottles(numBottles, numExchange) {
    let totalDrunk = numBottles;
    let empties = 0;
    let currentExRate = numExchange;
    while (numBottles > 0) {
        empties += numBottles;
        let newNumBottles = Math.floor(empties / currentExRate);
        empties = empties % currentExRate;
        numBottles = newNumBottles;
        totalDrunk += newNumBottles;
        currentExRate++;
    }
    return totalDrunk;
}

console.log(maxBottles(13, 6)); // Output: 15
console.log(maxBottles(10, 3)); // Output: 13;
#include <stdio.h>

int maxBottles(int numBottles, int numExchange) {
    int totalDrunk = numBottles;
    int empties = 0;
    int currentExRate = numExchange;
    while (numBottles > 0) {
        empties += numBottles;
        int newBottles = empties / currentExRate;
        empties = empties % currentExRate;
        numBottles = newBottles;
        totalDrunk += newBottles;
        currentExRate++;
    }
    return totalDrunk;
}

int main() {
    printf("%d\n", maxBottles(13, 6)); // Output: 15
    printf("%d\n", maxBottles(10, 3)); // Output: 13
    return 0;
}
using System;

public class WaterBottles {
    public static int MaxBottles(int numBottles, int numExchange) {
        int totalDrunk = numBottles;
        int empties = 0;
        int currentExRate = numExchange;
        while (numBottles > 0) {
            empties += numBottles;
            int newBottles = empties / currentExRate;
            empties = empties % currentExRate;
            numBottles = newBottles;
            totalDrunk += newBottles;
            currentExRate++;
        }
        return totalDrunk;
    }

    public static void Main() {
        Console.WriteLine(MaxBottles(13, 6)); // Output: 15
        Console.WriteLine(MaxBottles(10, 3)); // Output: 13
    }
}

Python's optimized syntactic expressions simplify mathematical calculations, producing results based on efficient flow guiding throughout, maintaining simplicity and power in reducing operations where feasible.

Complexity

Time Complexity: O(log(numBottles))
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Simulation

We can drink all the full water bottles at the beginning, so initially the amount of water we drink is numBottles. Then, we repeatedly perform the following operations:

  • If we currently have numExchange empty bottles, we can exchange them for one full bottle. After the exchange, the value of numExchange increases by 1. Then, we drink this bottle, increasing the total amount of water drunk by 1, and the number of empty bottles increases by 1.
  • If we do not have numExchange empty bottles, we cannot exchange for more water and should stop.

We repeat the above process until we can no longer exchange bottles. The total amount of water drunk is the answer.

The time complexity is O(\sqrt{n}), where n is the initial number of full bottles. The space complexity is O(1).

function maxBottlesDrunk(numBottles: number, numExchange: number): number {
    let ans = numBottles;
    while (numBottles >= numExchange) {
        numBottles -= numExchange;
        ++numExchange;
        ++ans;
        ++numBottles;
    }
    return ans;
}
func maxBottlesDrunk(numBottles int, numExchange int) int {
	ans := numBottles
	for numBottles >= numExchange {
		numBottles -= numExchange
		numExchange++
		ans++
		numBottles++
	}
	return ans
}
impl Solution {
    pub fn max_bottles_drunk(mut num_bottles: i32, mut num_exchange: i32) -> i32 {
        let mut ans = num_bottles;

        while num_bottles >= num_exchange {
            num_bottles -= num_exchange;
            num_exchange += 1;
            ans += 1;
            num_bottles += 1;
        }

        ans
    }
}
class Solution {
    /**
     * @param Integer $numBottles
     * @param Integer $numExchange
     * @return Integer
     */
    function maxBottlesDrunk($numBottles, $numExchange) {
        $ans = $numBottles;
        while ($numBottles >= $numExchange) {
            $numBottles -= $numExchange;
            $numExchange++;
            $ans++;
            $numBottles++;
        }
        return $ans;
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Iterative Simulation

Time Complexity: O(log(numBottles))
Space Complexity: O(1)

Mathematical Optimization

Time Complexity: O(log(numBottles))
Space Complexity: O(1)

Simulation–

Complexity analysis

ApproachTimeSpaceWhen to Use
Iterative SimulationO(k)O(1)Best for clarity and interviews where straightforward simulation of the rules is expected.
Mathematical OptimizationO(1)O(1)When you recognize the arithmetic progression pattern and want a constant-time calculation.

Frequently asked questions

Is Water Bottles II easy or hard?

Water Bottles II is typically classified as Medium difficulty. The base logic is straightforward simulation, but recognizing the mathematical shortcut and reasoning about increasing exchange cost adds an extra layer of difficulty.

Water Bottles II Python/Java solution

In Python or Java, implement a loop that tracks empty bottles and the current exchange cost. While empties are at least the required cost, perform an exchange, increment the total bottles drunk, and increase the cost by one. The implementation uses only a few integer variables and constant extra space.

How to solve Water Bottles II in O(1)?

Use a mathematical observation about the increasing exchange cost. If k exchanges occur, the costs form an arithmetic sequence starting from numExchange. Compute the total empties spent using the sum of that sequence and ensure the remaining empties stay non‑negative. Solving the inequality gives the maximum k, and the final result is numBottles + k.

What is the best approach for Water Bottles II?

The most practical approach is iterative simulation. Track the number of empty bottles, repeatedly exchange them for a new bottle, and increase the exchange cost after each trade. This runs in O(k) time where k is the number of exchanges and uses O(1) space. Many candidates present this first in interviews because it mirrors the problem rules directly.

Is Water Bottles II asked at Google/Amazon/Meta?

Problems involving simulation and mathematical reasoning appear frequently in interviews at large tech companies. While this exact question may not always appear, similar exchange-process or resource-simulation problems are common screening exercises at companies like Amazon and Google.

What data structure is used in Water Bottles II?

No advanced data structure is required. The problem mainly relies on integer variables and arithmetic updates. It falls under simulation and math categories rather than structures like arrays, stacks, or hash maps.

What is the time complexity of Water Bottles II?

The standard simulation solution runs in O(k) time where k is the number of exchanges performed. Each loop iteration handles one exchange and updates the required cost. A mathematical optimization can reduce this to O(1) time by computing the number of valid exchanges using arithmetic progression formulas.

Comments

Next problem · similarWater BottlesEasy
Now write it yourselfClose this page and solve Water Bottles II in the editor, without looking.
Practise Water Bottles II