題目連結(https://leetcode.com/problems/water-bottles/description/?envType=daily-question&envId=2025-10-01)

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.

每日一題，數學題，有關商和餘數的處理與模擬

1. Repeat（題目重複確認）

• 輸入：兩個整數 初始滿瓶numBottles, 兌換比例numExchange
• 輸出：可喝到的最多水瓶數
• 前提：
  • 1 <= numBottles <= 100
  • 2 <= numExchange <= 100

2. Examples（舉例確認理解）

原本有 15 個滿瓶，4 個空瓶可換 1 個滿瓶

15/4 = 3…2 ，15 個空瓶可換 3 個滿瓶，剩下 2 個空瓶

q=3, c=2，3 個滿瓶喝完變 3 個空瓶 加上 2 個空瓶

(2+3) /4 =1…1，5 個空瓶可換 1 個滿瓶，剩下 1 個空瓶

q=1, c=1

(1+1)/4 = 0…2，換不了，剩下 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.

3. Approach（解題思路）

方法 ：迭代模擬法 (Iterative Simulation)

模擬一個重複的兌換過程直到無法兌換為止。由於兌換過程每次會消耗 numExchange 個空瓶，並產生 1 個滿瓶，我們可以持續利用長除法來計算能兌換的次數。

• 時間複雜度：O(logn) 或 O(1)
• 雖然有 while 迴圈，但每次兌換的空瓶數 k 接近於 k/numExchange。由於 numExchange≥2，每次迭代空瓶數會以指數級速度減少。因此，迭代次數是 O(lognumExchange(numBottles))。在約束範圍很小時，這通常被視為非常快，甚至可以簡化為 O(1)（因為迭代次數是固定的上限）。
• 空間複雜度：O(1)

4. Code（C++）

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int q = numBottles / numExchange; // 第一次換到的滿瓶數（商）
        int r = numBottles % numExchange; // 第一次剩下的空瓶數（餘）
        int result = numBottles + q;      // 總共喝掉 = 初始 + 第一次換到的

        while (q + r >= numExchange) {
            int empty = (q + r);          // q 是「新喝完的瓶」，c 是「剩下的空瓶」
            q = empty / numExchange;      // 再次兌換
            r = empty % numExchange;      // 再次剩餘
            result += q;
        }
        return result;
    }
};

5. Test 範例

• numBottles = 15，numExchange = 4
• 初始化
  • 15/4 = 3…2
  • q=3, r=2
  • result = 15+3 = 18
• 第 1 輪 (While loop):
  • q+r = (2+3) /4 =1…1
  • q=1, r=1
  • result = 18+1 = 19
• 第 2 輪 (While loop):
  • q+r = (1+1)/4 = 0…2 < numExchange(=4)
  • 結束迴圈
• return result，output = 19

6. 相關題目與延伸概念

• 3100. Water Bottles II

7. 補充：語法＆注意事項

1. 遞迴地應用 q=n/d, r=n%d 的數學性質
2. 兌換系統的題目經常出現在簡化版的分數應用（例如：一個披薩可以換多少塊，剩下的邊角料再換成一塊披薩...）中，核心想法都是透過 while 迴圈來模擬最終的收斂過程。

ps. 部分內容經 AI 協助整理