# Water Bottles
**Difficulty:** EASY
[External](https://leetcode.com/problems/water-bottles)
Canonical: https://scaleengineer.com/dsa/problems/water-bottles
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Amadeus](https://scaleengineer.com/companies/amadeus), [HiLabs](https://scaleengineer.com/companies/hilabs)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/water-bottles/image0.png) 

**Input:** numBottles = 9, numExchange = 3
**Output:** 13
**Explanation:** You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

**Example 2:**

![](https://assets.glich.co/dsa/water-bottles/image1.png) 

**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.

**Constraints:**

* `1 <= numBottles <= 100`
* `2 <= numExchange <= 100`

# Approaches
## Iterative Simulation
This approach directly simulates the process of drinking bottles and exchanging empty ones for full ones. We use a loop that continues as long as we can obtain new bottles from exchanges. In each iteration, we calculate how many new bottles can be acquired, add them to our count of drinks, and update the number of empty bottles for the next round.
**Time:** O(log_{numExchange}(numBottles)). In each iteration, the number of empty bottles is roughly divided by `numExchange`. The number of iterations is therefore logarithmic with respect to the initial number of bottles. · **Space:** O(1). We only use a few variables to keep track of the counts, regardless of the input size.
**Pros:** Intuitive and easy to understand as it directly models the problem statement.; Correct for all edge cases covered by the constraints.
**Cons:** Slightly less performant than a direct mathematical solution, although very fast for the given constraints.
### Explanation
We start by drinking all the initial `numBottles`. This sets our initial `totalDrunk` count and gives us `numBottles` empty bottles. Then, we enter a loop that continues as long as we have enough empty bottles to make an exchange (i.e., `emptyBottles >= numExchange`).

Inside the loop:
1.  We calculate how many new full bottles we can get by dividing the current number of `emptyBottles` by `numExchange`.
2.  We add this number of `newBottles` to our `totalDrunk` count.
3.  We update our count of `emptyBottles`. The new count will be the sum of the bottles we just drank (`newBottles`) and any empty bottles that were left over from the exchange (`emptyBottles % numExchange`).

The loop terminates when we can no longer make any exchanges. The final `totalDrunk` is the result.

```java
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int totalDrunk = numBottles;
        int emptyBottles = numBottles;

        while (emptyBottles >= numExchange) {
            int newBottles = emptyBottles / numExchange;
            totalDrunk += newBottles;
            emptyBottles = (emptyBottles % numExchange) + newBottles;
        }

        return totalDrunk;
    }
}
```
### Algorithm
- Initialize `totalDrunk` to `numBottles`.
- Initialize `emptyBottles` to `numBottles`.
- Loop as long as `emptyBottles >= numExchange`:
  - Calculate `newBottles = emptyBottles / numExchange`.
  - Increment `totalDrunk` by `newBottles`.
  - Update `emptyBottles = (emptyBottles % numExchange) + newBottles`.
- Return `totalDrunk`.

## O(1) Mathematical Approach
A more advanced approach involves deriving a mathematical formula to solve the problem in constant time. By analyzing the net cost of empty bottles for each extra drink, we can find a direct relationship between the initial number of bottles and the total number of drinks.
**Time:** O(1). The solution involves a few arithmetic operations, which take constant time. · **Space:** O(1). No extra space is used that depends on the input size.
**Pros:** Extremely efficient, providing a solution in constant time.; Elegant and concise.
**Cons:** The derivation of the formula is non-obvious and requires careful reasoning about the problem's mechanics.
### Explanation
Let's analyze the exchange process from a different perspective. To obtain one new full bottle, we must trade `numExchange` empty bottles. After we drink this new bottle, it becomes an empty bottle itself. So, for every extra bottle we drink, we effectively reduce our total stock of empty bottles by `numExchange - 1`.

We start with `numBottles` full bottles. After drinking them, we have `numBottles` empty bottles. These are the 'currency' we can use for exchanges. The question becomes: how many times can we 'pay' the price of `numExchange - 1` empty bottles when we start with `numBottles` empty bottles?

One might think the answer is `numBottles / (numExchange - 1)`. However, we can't trade our very last empty bottle. The process must stop when we have fewer than `numExchange` bottles, and we can't get stuck with zero empty bottles and still be able to exchange. So, the total number of empty bottles we can afford to give up permanently is `numBottles - 1`.

The number of extra drinks (exchanges) we can get is `(numBottles - 1) / (numExchange - 1)`.

Therefore, the total number of bottles we can drink is the initial `numBottles` plus these extra drinks.

**Formula:** `totalDrunk = numBottles + (numBottles - 1) / (numExchange - 1)`

This formula works even for edge cases. If `numBottles < numExchange`, then `numBottles - 1 < numExchange - 1`, and the integer division correctly results in 0 extra bottles.

```java
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // Each exchange for a new bottle costs `numExchange` empty bottles,
        // but we get one back after drinking it. The net cost is `numExchange - 1` empty bottles.
        // We start with `numBottles` empty bottles after drinking the initial set.
        // We can't use the very last empty bottle in an exchange, so we effectively have
        // `numBottles - 1` empty bottles to 'spend' on the net cost.
        // The number of extra bottles we can get is (numBottles - 1) / (numExchange - 1).
        if (numBottles < numExchange) {
            return numBottles;
        }
        return numBottles + (numBottles - 1) / (numExchange - 1);
    }
}
```
### Algorithm
- Calculate the number of extra bottles that can be obtained through exchanges using the formula: `extraBottles = (numBottles - 1) / (numExchange - 1)`.
- The total number of drunk bottles is the sum of the initial bottles and the extra bottles: `totalDrunk = numBottles + extraBottles`.
- Return `totalDrunk`.

# Solutions
### Java

```java
class Solution {
public
  int numWaterBottles(int numBottles, int numExchange) {
    int ans = numBottles;
    for (; numBottles >= numExchange; ++ans) {
      numBottles -= (numExchange - 1);
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number} numBottles * @param {number} numExchange * @return {number} */ var numWaterBottles = function ( numBottles , numExchange ) { let ans = numBottles ; for (; numBottles >= numExchange ; ++ ans ) { numBottles -= numExchange - 1 ; } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  int numWaterBottles(int numBottles, int numExchange) {
    int ans = numBottles;
    for (; numBottles >= numExchange; ++ans) {
      numBottles -= (numExchange - 1);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int: ans = numBottles while numBottles >= numExchange: numBottles -= numExchange - 1 ans += 1 return ans

```