Skip to main content
Talentd

Water Bottles II - Solution & Explanation

MediumMathSimulation19 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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.

This C code continuously drinks bottles by reducing the number of full bottles to zero in each iteration. It then calculates how many new full bottles can be obtained by exchanging empty bottles, and updates the exchange rate for future iterations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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.

In this method, while maintaining a count of total bottles drunk, we keep track of empty bottles, using integer division to calculate full bottles. The exchange rate is incremented at each step as per rules, and results calculated in fewer operations by concentrating on full/empty relationships.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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

Code

PythonJavaC++GoTypeScriptRustC#PHP

Python

Java

C++

Go

TypeScript

Rust

C#

PHP

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—

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

Video Solution

Water Bottles II | 2 Approaches | Sridharacharya formula | Leetcode 3100 | codestorywithMIK • codestorywithMIK • 4,131 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Water Bottles II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Water Bottles