Skip to main content
Talentd

Water Bottles - Solution & Explanation

EasyMathSimulation12 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

 

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

 

Constraints:

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

Approach Overview

Problem Overview: You start with numBottles full water bottles. After drinking a bottle you keep the empty one. Every numExchange empty bottles can be traded for one new full bottle. The task is to compute the maximum number of bottles you can drink.

The core idea is simple: every bottle eventually becomes an empty bottle that may help you obtain another full bottle. The challenge is tracking how exchanges accumulate over time.

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

This approach directly models the process described in the problem. Start by drinking all numBottles, which gives you the same number of empty bottles. As long as you have at least numExchange empties, exchange them for new full bottles. Each exchange increases the total bottles drunk and updates the empty bottle count.

The implementation uses a loop: compute how many new bottles you can obtain with integer division, add them to the total consumed, and update the remaining empties using modulo plus the new empties created by drinking. This is a classic simulation pattern where the code mirrors the real-world process step by step.

This method is easy to reason about and safe for interviews. Time complexity is O(n) where n is roughly the number of bottles consumed through exchanges, and space complexity is O(1) since only a few counters are maintained.

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

Instead of simulating every exchange, observe the pattern of bottle consumption. Every time you exchange bottles, you effectively spend numExchange empty bottles to gain one full bottle, but after drinking it you get one empty bottle back. The net cost of producing one extra drink becomes numExchange - 1 empty bottles.

This leads to a compact formula. Starting with numBottles bottles, the number of additional bottles you can drink through exchanges is (numBottles - 1) / (numExchange - 1). Add this value to the initial bottles to get the final answer. This relies on a small piece of math reasoning that compresses the entire simulation into constant time.

The mathematical solution runs in O(1) time and O(1) space because it performs only a few arithmetic operations. It is elegant and optimal once you recognize the invariant created by the exchange rule.

Recommended for interviews: Start with the iterative simulation because it clearly demonstrates understanding of the exchange mechanics and uses straightforward logic. After that, mention the mathematical shortcut as an optimization. Interviewers often appreciate candidates who first build the correct simulation and then derive the O(1) formula from the observation that each extra drink effectively costs numExchange - 1 empties.

Approach 1: Iterative Simulation

This approach uses a simple iterative simulation to solve the problem. We keep track of the current number of full bottles and empty bottles. We repeatedly drink a full bottle and calculate how many empty bottles we have. If the number of empty bottles is enough to exchange for a new full bottle, we perform the exchange and continue the loop. This process is repeated until no more exchanges can be made.

The function numWaterBottles calculates the maximum number of water bottles one can drink. It uses a loop to repeatedly simulate drinking and exchanging bottles while keeping track of total bottles drunk and current empty bottles.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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

Try this approach in the editor →

Approach 2: Mathematical Approach

This approach leverages a mathematical understanding of the problem. Instead of simulating every exchange, you can calculate how many overall bottles you'll get by using a formula. This involves understanding the number of bottles resulting from continuous exchanges until no more can be made.

In this C solution, a while loop is used to calculate the total number of bottles drunk by updating the current bottles with the new one obtained from the exchange.

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: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScriptPHP

Python

Java

C++

Go

TypeScript

JavaScript

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Simulation

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

Mathematical Approach

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

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative SimulationO(n)O(1)Best when explaining logic step‑by‑step or implementing the straightforward interpretation of the problem.
Mathematical FormulaO(1)O(1)Use when optimizing after recognizing the pattern that each extra drink effectively costs (numExchange − 1) empty bottles.

Video Solution

LeetCode 1518 | Water Bottles | Day 5 | 100_Days_LeetCode_Challenge | Master DSA with edSlash • edSlash • 30,897 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Water Bottles easy or hard?
Water Bottles is classified as an Easy problem with a high acceptance rate around 70%+. The simulation solution is straightforward, and the challenge mainly lies in recognizing the mathematical shortcut that converts the process into a constant-time calculation.
Water Bottles Python/Java solution
In Python or Java, the common implementation uses a loop that continues while empty bottles are greater than or equal to numExchange. Each iteration computes new bottles from integer division, updates the total drinks, and tracks remaining empties. The logic uses only a few variables and runs in O(n) time with constant space.
How to solve Water Bottles in O(1)?
Use the observation that exchanging numExchange empty bottles for one full bottle returns one empty after drinking. The net cost per additional drink becomes numExchange − 1 empties. The maximum bottles you can drink equals numBottles + (numBottles − 1) / (numExchange − 1), which computes the result in constant time.
What is the best approach for Water Bottles?
Two common approaches exist: iterative simulation and a mathematical formula. The simulation method repeatedly exchanges empty bottles for full ones and runs in O(n) time with O(1) space. The mathematical approach derives that each extra drink costs (numExchange − 1) empty bottles, producing an O(1) time solution.
Is Water Bottles asked at Google/Amazon/Meta?
Water Bottles is a typical easy-level interview problem focused on simulation and simple mathematical reasoning. Similar exchange or resource-conversion problems appear in interviews at large tech companies including Amazon and Google as warm-up or screening questions.
What data structure is used in Water Bottles?
No specialized data structure is required. The solution relies on integer arithmetic and counters to track full bottles, empty bottles, and exchanges. It primarily tests simulation logic and mathematical reasoning rather than data structure design.
What is the time complexity of Water Bottles?
The simulation approach runs in O(n) time where n is the number of bottles consumed through exchanges, with constant O(1) space. The optimized mathematical solution reduces the complexity to O(1) time and O(1) space by computing the result directly using arithmetic.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Water Bottles II