💬 Discord
Sign In
NeetCode #891LC-1518EasyMath & Geometry
← Back to All Problems

#891 · #1518 · Water Bottles(换水问题)

📌 Problem Statement & Constraints

You start with numBottles full water bottles. You may exchange numExchange empty bottles for one full bottle. Return the maximum number of bottles you can drink. Constraints: 1 <= numBottles <= 100, 2 <= numExchange <= 100.

💡 Core Algorithmic Approaches

  1. Drink all full bottles, accumulating their empties.
  2. While the empty count is at least numExchange, exchange as many groups as possible for full bottles.
  3. Each newly obtained bottle adds to the drink total and, once drunk, becomes empty again, so it rejoins the pool.
  4. Repeat until fewer than numExchange empties remain.

💻 Benchmark Python3 Implementation

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        total = numBottles
        empty = numBottles
        while empty >= numExchange:
            new = empty // numExchange      # bottles gained this round
            total += new
            empty = empty % numExchange + new   # leftover + newly emptied
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) iterations: the empty count shrinks geometrically.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to add the new bottles back into the empty pool: the loop would stall after one round.
  • Exchanging one bottle per iteration: correct but slower than batching with // and %.
  • Stopping when empty == numExchange: at equality one more exchange is still possible, so the condition is >=.
  • Using empty = empty // numExchange: that discards the remainder, which must be carried forward.