Problem 1518

Abstract / Summary

Given full and empty bottles, determine how many drinks can be had by exchanging empties for full ones.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1518.py

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        result = 0
        full   = numBottles
        empty  = 0
        # no fancy math, just simulation
        while full > 0 or empty >= numExchange:
            if full > 0:
                result += 1
                full   -= 1
                empty  += 1
            if empty >= numExchange:
                full   += 1
                empty  -= numExchange
        return result
15 lines | 493 bytes | submitted December 17, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 73% (600k+ submissions).

Typical patterns to solve this problem:
  • Math
  • Simulation
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation solves the classic “water bottle exchange” problem by simulating the drinking and exchange process. It maintains three counters: the total number of bottles consumed (result), the number of full bottles currently available (full), and the number of empty bottles on hand (empty). The algorithm repeatedly drinks a full bottle when possible and exchanges a set of empty bottles for a new full one, stopping only when no further actions can be performed.

Core Logic

The initialization establishes the starting state based on the input parameters:

result = 0
full   = numBottles
empty  = 0

The main loop drives the simulation. It continues while there is at least one full bottle to drink or enough empty bottles to perform an exchange:

while full > 0 or empty >= numExchange:

Inside the loop, the first conditional block models the act of drinking a bottle. When a full bottle exists, the total count of consumed bottles is incremented, the full bottle count is decremented, and the empty bottle count is incremented:

if full > 0:
    result += 1
    full   -= 1
    empty  += 1

The second conditional block handles the exchange operation. Whenever the number of empty bottles meets or exceeds the exchange threshold, a new full bottle is obtained and the appropriate number of empty bottles are removed:

if empty >= numExchange:
    full   += 1
    empty  -= numExchange

When the loop terminates, the accumulated result reflects the maximum number of bottles that can be drunk given the exchange rules:

return result

Edge Cases Handled

The simulation naturally accommodates scenarios where the initial number of bottles is zero. In that case, full starts at zero, the loop condition fails because empty is also zero, and the function returns zero without entering the loop.

When the exchange rate (numExchange) is larger than the total number of bottles that could ever become empty, the second conditional never triggers. The algorithm still correctly counts the consumption of the initial bottles and exits once full reaches zero.

If the exchange rate is one, every empty bottle immediately yields a new full bottle. The loop continues indefinitely in a naïve implementation, but here the condition full > 0 or empty >= numExchange ensures progress: each iteration consumes one bottle and immediately creates another, effectively counting each bottle exactly once before the loop ends when full becomes zero and no empty bottles remain.

The code also gracefully handles the situation where numExchange equals the initial number of bottles. After drinking all initial bottles, the accumulated empties meet the exchange threshold, producing exactly one additional full bottle, which is then consumed in the next iteration.

Performance Optimizations

The algorithm avoids any heavy arithmetic or recursion, relying solely on simple integer increments, decrements, and comparisons. By using a single while loop with two lightweight condition checks, it minimizes overhead per iteration. The use of direct variable updates (result += 1, full -= 1, empty += 1) ensures that the interpreter can execute each step with minimal bytecode instructions.

Because the loop condition incorporates both full and empty thresholds, the simulation terminates as soon as no further actions are possible, preventing unnecessary iterations. The code does not allocate additional data structures or perform costly list operations, keeping memory usage constant throughout execution.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a line of sparkling water bottles sitting on a table. The goal is to drink as many as possible. Every time a bottle is finished, it becomes an empty glass bottle. If there are enough empty bottles, they can be taken to a magical shop to be exchanged for one brand new, full bottle of water.

The code works exactly like this game. It starts by taking every full bottle one by one and drinking them until the supply is gone. Each time a drink is finished, the number of empty bottles grows by one. The computer keeps a careful watch on the empty bottles. Whenever the group of empty bottles reaches the magic number needed for an exchange, the computer trades them in.

Those traded bottles turn back into a full bottle, so the process can happen all over again. The computer repeats this cycle of drinking and trading until it is physically impossible to get any more full bottles. It keeps track of every single drink taken along the way until the very end.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.19 | σ = 1.19

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++
leetcode.ca C++ Python Java JS Go PHP TS
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
fartem Ruby
FelixFan1122 Java
fsq C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
withaarzoo C++
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++
leetcode.ca C++, Go, Java, JavaScript, PHP, Python, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
fartem Ruby
FelixFan1122 Java
fsq C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
suxrobGM C#
trung-hn Python
varunu28 Java
withaarzoo C++
YuriSpiridonov Python
32 links | 21 authors | 10 languages

Videos

9 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

2 solutions   December 17, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality