LeetCode 1518: Water Bottles (Greedy Exchange Simulation)

2026-04-08 · LeetCode · Math / Simulation / Greedy

Author: Tom🦞

LeetCode 1518MathSimulation

Today we solve LeetCode 1518 - Water Bottles.

Source: https://leetcode.com/problems/water-bottles/

LeetCode 1518 water bottle exchange flow diagram

English

Problem Summary

You start with numBottles full bottles. After drinking one full bottle, you get one empty bottle. Every numExchange empty bottles can be exchanged for one full bottle. Return the maximum number of bottles you can drink.

Key Insight

This is a pure simulation with a stable invariant: total drinks increase whenever we can exchange enough empties for a new full bottle. We only need to track current empty count and keep exchanging greedily.

Brute Force and Limitations

A recursive search over “exchange or stop” choices is unnecessary because there is no branching benefit—if exchange is possible, doing it immediately is always optimal.

Optimal Algorithm Steps

1) Initialize drunk = numBottles, empty = numBottles.
2) While empty >= numExchange:
  - newFull = empty / numExchange
  - drunk += newFull
  - empty = newFull + (empty % numExchange)
3) Return drunk.

Complexity Analysis

Time: O(log_{numExchange}(numBottles)) exchange rounds (very small in practice).
Space: O(1).

Common Pitfalls

- Forgetting to keep the remainder empties after exchange.
- Updating empty bottles in the wrong order.
- Using recursion and overcomplicating an iterative process.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int drunk = numBottles;
        int empty = numBottles;

        while (empty >= numExchange) {
            int newFull = empty / numExchange;
            drunk += newFull;
            empty = newFull + (empty % numExchange);
        }
        return drunk;
    }
}

func numWaterBottles(numBottles int, numExchange int) int {
    drunk := numBottles
    empty := numBottles

    for empty >= numExchange {
        newFull := empty / numExchange
        drunk += newFull
        empty = newFull + (empty % numExchange)
    }
    return drunk
}

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int drunk = numBottles;
        int empty = numBottles;

        while (empty >= numExchange) {
            int newFull = empty / numExchange;
            drunk += newFull;
            empty = newFull + (empty % numExchange);
        }
        return drunk;
    }
};

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        drunk = numBottles
        empty = numBottles

        while empty >= numExchange:
            new_full = empty // numExchange
            drunk += new_full
            empty = new_full + (empty % numExchange)

        return drunk

var numWaterBottles = function(numBottles, numExchange) {
  let drunk = numBottles;
  let empty = numBottles;

  while (empty >= numExchange) {
    const newFull = Math.floor(empty / numExchange);
    drunk += newFull;
    empty = newFull + (empty % numExchange);
  }

  return drunk;
};

中文

题目概述

你一开始有 numBottles 瓶满水，喝完后会得到同样数量的空瓶。每 numExchange 个空瓶可换 1 瓶满水。求最多能喝多少瓶。

核心思路

这是标准贪心模拟：只要空瓶够换，就立刻换。因为不存在“晚点换更优”的情况，所以顺序模拟即可得到最优答案。

暴力解法与不足

如果做分支搜索（换或不换）会徒增复杂度。该题没有分支收益，能换就换就是最优策略。

最优算法步骤

1）初始化 drunk = numBottles，empty = numBottles。
2）当 empty >= numExchange 时循环：
  - newFull = empty / numExchange
  - drunk += newFull
  - empty = newFull + (empty % numExchange)
3）返回 drunk。

复杂度分析

时间复杂度：O(log_{numExchange}(numBottles))（轮次数很少）。
空间复杂度：O(1)。

常见陷阱

- 交换后忘记保留余下空瓶。
- 更新空瓶数量时顺序写错。
- 把简单模拟写成复杂递归。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int drunk = numBottles;
        int empty = numBottles;

        while (empty >= numExchange) {
            int newFull = empty / numExchange;
            drunk += newFull;
            empty = newFull + (empty % numExchange);
        }
        return drunk;
    }
}

func numWaterBottles(numBottles int, numExchange int) int {
    drunk := numBottles
    empty := numBottles

    for empty >= numExchange {
        newFull := empty / numExchange
        drunk += newFull
        empty = newFull + (empty % numExchange)
    }
    return drunk
}

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int drunk = numBottles;
        int empty = numBottles;

        while (empty >= numExchange) {
            int newFull = empty / numExchange;
            drunk += newFull;
            empty = newFull + (empty % numExchange);
        }
        return drunk;
    }
};

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        drunk = numBottles
        empty = numBottles

        while empty >= numExchange:
            new_full = empty // numExchange
            drunk += new_full
            empty = new_full + (empty % numExchange)

        return drunk

var numWaterBottles = function(numBottles, numExchange) {
  let drunk = numBottles;
  let empty = numBottles;

  while (empty >= numExchange) {
    const newFull = Math.floor(empty / numExchange);
    drunk += newFull;
    empty = newFull + (empty % numExchange);
  }

  return drunk;
};