# Water Bottles II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/water-bottles-ii)
Canonical: https://scaleengineer.com/dsa/problems/water-bottles-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
You are given two integers `numBottles` and `numExchange`.

`numBottles` represents the number of full water bottles that you initially have. In one operation, you can perform one of the following operations:

* Drink any number of full water bottles turning them into empty bottles.
* Exchange `numExchange` empty bottles with one full water bottle. Then, increase `numExchange` by one.

Note that you cannot exchange multiple batches of empty bottles for the same value of `numExchange`. For example, if `numBottles == 3` and `numExchange == 1`, you cannot exchange `3` empty water bottles for `3` full bottles.

Return _the **maximum** number of water bottles you can drink_.

**Example 1:**

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

**Input:** numBottles = 13, numExchange = 6
**Output:** 15
**Explanation:** The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

**Example 2:**

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

**Input:** numBottles = 10, numExchange = 3
**Output:** 13
**Explanation:** The table above shows the number of full water bottles, empty water bottles, the value of numExchange, and the number of bottles drunk.

**Constraints:**

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

# Approaches
## Naive Simulation
This approach directly simulates the process described in the problem statement by handling one bottle at a time. It maintains counts of full and empty bottles and iteratively performs either a drinking or an exchanging operation in a loop until no more actions are possible. This method is straightforward but not the most efficient.
**Time:** O(D), where D is the total number of bottles drunk. The loop runs for each exchange and for each batch of drinking. The total number of bottles drunk is `numBottles` plus the number of exchanges (`k`). The complexity is roughly `O(numBottles + k)`. Given the constraints, this is dominated by `numBottles`. · **Space:** O(1) - We only use a few variables to store the state (full bottles, empty bottles, etc.), so the space required is constant.
**Pros:** The logic is very simple and directly follows the rules given in the problem description.; It's easy to implement and debug.
**Cons:** This approach is less efficient because it processes each bottle individually, leading to a higher number of loop iterations.; The number of iterations is proportional to the total number of bottles drunk, which can be significantly larger than the number of exchanges.
### Explanation
In this naive simulation, we use a loop that continues as long as we can either drink a bottle or perform an exchange. The state of our simulation is tracked using variables for the number of full bottles, empty bottles, and the current exchange rate.

Inside the loop, we prioritize drinking. If there are any full bottles, we simulate drinking one, which increments our total `drunkCount` and adds one to our `emptyBottles` stock. If there are no full bottles left, we check if we have accumulated enough empty bottles to make an exchange. If `emptyBottles` is greater than or equal to the current `numExchange`, we perform the trade. This gives us one new full bottle and increases the `numExchange` requirement for the next trade. The simulation terminates when we have no full bottles to drink and not enough empty ones to make an exchange.

```java
class Solution {
    public int waterBottlesII(int numBottles, int numExchange) {
        int fullBottles = numBottles;
        int emptyBottles = 0;
        int drunkCount = 0;
        
        while (true) {
            if (fullBottles > 0) {
                // Drink one bottle at a time
                drunkCount += fullBottles;
                emptyBottles += fullBottles;
                fullBottles = 0;
            } else if (emptyBottles >= numExchange) {
                // Exchange for a new bottle
                emptyBottles -= numExchange;
                fullBottles++;
                numExchange++;
            } else {
                // Cannot drink or exchange, so we stop
                break;
            }
        }
        return drunkCount;
    }
}
```
This version of the code is slightly optimized from a true one-by-one simulation by drinking all available bottles at once, but the logic remains step-by-step, alternating between drinking and exchanging phases.
### Algorithm
- Initialize variables: `fullBottles` to `numBottles`, `emptyBottles` to 0, `drunkCount` to 0, and `currentExchange` to `numExchange`.
- Start an infinite loop to simulate the process.
- Inside the loop, check if there are full bottles to drink.
  - If `fullBottles > 0`, drink one bottle. This means decrementing `fullBottles`, and incrementing `emptyBottles` and `drunkCount`.
- If there are no full bottles, check if an exchange is possible.
  - If `emptyBottles >= currentExchange`, perform an exchange. Decrement `emptyBottles` by `currentExchange`, increment `fullBottles` by 1, and increment `currentExchange` by 1.
- If neither drinking nor exchanging is possible, break the loop.
- Return the final `drunkCount`.

## Optimized Simulation
This approach improves upon the naive simulation by processing bottles in batches. The key insight is that there is no benefit to holding onto full water bottles. It's always optimal to drink them as soon as they are available to maximize the number of empty bottles for exchanges. This significantly reduces the number of operations and loop iterations required.
**Time:** O(k), where k is the total number of exchanges made. The value of `numExchange` increases with each iteration, so the number of empty bottles required grows, leading to a rapid termination of the loop. The number of exchanges `k` is approximately `O(sqrt(numBottles))`, making this solution very fast. · **Space:** O(1) - The approach uses a constant amount of extra space for variables, regardless of the input size.
**Pros:** Highly efficient, as the number of loop iterations is equal to the number of exchanges, which is very small.; The logic is still quite straightforward and easy to follow.
**Cons:** Requires the small insight that it's always optimal to drink all available bottles immediately.
### Explanation
We can optimize the simulation by realizing that the best strategy is to convert all full bottles into empty ones as quickly as possible. This maximizes the number of empty bottles available for the current exchange rate.

First, we drink all the initial `numBottles`. This sets our initial `drunkCount` and `emptyBottles` to `numBottles`.

Then, we enter a loop that continues as long as we can make an exchange. The condition for the loop is `emptyBottles >= numExchange`. In each iteration, we simulate one exchange: we use `numExchange` empty bottles to get one new full bottle, and `numExchange` is then incremented. We immediately drink this new bottle. This single action increments our `drunkCount` by one and also adds one to our `emptyBottles` count. The loop continues with the updated values until we can no longer afford an exchange.

```java
class Solution {
    public int waterBottlesII(int numBottles, int numExchange) {
        int drunkCount = numBottles;
        int emptyBottles = numBottles;

        while (emptyBottles >= numExchange) {
            // Perform one exchange
            emptyBottles -= numExchange;
            numExchange++;
            
            // Drink the new bottle obtained from the exchange
            drunkCount++;
            emptyBottles++; // The newly drunk bottle becomes an empty one
        }
        
        return drunkCount;
    }
}
```
### Algorithm
- Initialize `drunkCount` to `numBottles`, as we drink all initial bottles.
- Initialize `emptyBottles` to `numBottles`.
- Start a loop that continues as long as `emptyBottles` is greater than or equal to the current `numExchange`.
- Inside the loop, perform one exchange operation:
  - Decrement `emptyBottles` by `numExchange`.
  - Increment `numExchange` for the next potential trade.
- The exchange gives one new full bottle, which we immediately drink:
  - Increment `drunkCount` by 1.
  - Increment `emptyBottles` by 1 (as the new bottle becomes empty).
- Once the loop terminates, return the total `drunkCount`.

# Solutions
### Java

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

### CPP

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

### Python

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