1518. Water Bottles || LeetCode || C++

Solving LeetCode problem 1518. Water Bottles with a simple greedy approach in C++.

---

Intuition

We are given a number of full bottles and a rule that allows exchanging empty bottles for new full ones.

At first glance, this is similar to repeatedly trading resources:

every time we have enough empty bottles, we can exchange them for more full bottles.

The total number of bottles consumed will be the sum of:

• Initially available bottles
• Plus all future bottles obtained by exchanges.

---

Approach

1. Start with numBottles full bottles, so the total consumed begins at numBottles.
2. After drinking them, we gain the same number of empty bottles.
3. While the number of empty bottles is greater than or equal to numExchange:
   • Exchange as many as possible: t = numBottles / numExchange (new bottles obtained).
   • Add t to the total consumed count.
   • Compute the remaining bottles after exchange: rem = numBottles % numExchange.
   • The new count of empty bottles becomes t + rem.
4. Repeat until exchanges are no longer possible.
5. Return the total consumed.

This greedy approach works because each exchange step maximizes the number of bottles we can drink at that stage.

---

Complexity

• Time complexity:
  
  Each loop iteration reduces the number of bottles by at least 1, so the loop runs at most O(numBottles) times.
  
  Effectively, the complexity is closer to O(log(numBottles)) since bottles shrink quickly with division.

• Space complexity:
  
  We only use a few extra variables (t, rem, numOfBottles), so the space usage is O(1).

---

Code (C++)

cpp
class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int numOfBottles = numBottles;

        while (numBottles >= numExchange) {
            int t = numBottles / numExchange; // number of new bottles obtained
            int rem = numBottles % numExchange; // leftover bottles
            numOfBottles += t;
            numBottles = t + rem; // update for next round
        }

        return numOfBottles;
    }
};