1518. Water Bottles

Intuition

The problem requires determining the maximum number of water bottles that can be consumed, considering the ability to exchange empty bottles for full ones. Initially, you have a certain number of full water bottles (numBottles). Each time you drink a bottle, it turns into an empty bottle, and once you accumulate enough empty bottles (numExchange), you can trade them for a new full bottle.

The intuition is to continuously keep track of the number of full and empty bottles, ensuring to maximize the drinking process by always exchanging empty bottles for full ones when possible.

Approach

1. Initial Setup: Start with the given number of full bottles (numBottles).
2. Drink and Exchange: Implement a loop where, in each iteration, you: - Drink all the current full bottles, adding to the total count of bottles drunk. - Convert all these full bottles into empty bottles. - Exchange as many empty bottles as possible for new full bottles. - Keep any remaining empty bottles that couldn't be exchanged.
3. Repeat: Continue this process until no more exchanges can be made (i.e., when the number of empty bottles is less than numExchange).
4. Terminate: Return the total count of bottles drunk as the result.

In terms of implementation, we can use a while loop to simulate this process, updating the count of full and empty bottles at each step.

Formula Derivation

To derive the formula numBottles + (numBottles - 1) // (numExchange - 1), let's break down the process and understand how it accounts for the maximum number of water bottles you can drink:

Step-by-Step Explanation

1. Initial Full Bottles: Start with numBottles full bottles.
2. Drinking and Exchanging: - For each bottle you drink, you get one empty bottle. - You can exchange numExchange empty bottles for one full bottle.
3. Counting Bottles: - Initially, you can drink numBottles full bottles. - After drinking, you will have numBottles empty bottles. - To determine how many additional full bottles you can get from exchanges, note that for every numExchange empty bottles, you get one full bottle.

Simplified Calculation

Instead of simulating the process, observe the relationship between the number of bottles and exchanges:

1. Total Bottles Drunk: - Let's denote the total number of bottles you can drink by T.
2. Exchanges Needed: - Each exchange gives one full bottle for numExchange empty bottles. - After each exchange, the number of empty bottles reduces and needs to be recalculated.
3. Formula Derivation: - The key insight is to recognize a pattern in the exchanges. Specifically, each exchange reduces the total count of bottles by numExchange - 1 (because one bottle is gained while numExchange empty bottles are used up). - Therefore, the total number of bottles drunk, considering initial bottles and exchanges, can be calculated directly without iterating.

General Formula

Combining these insights, the total number of bottles drunk can be expressed as:

\[ T = numBottles + floor((numbottles - 1) / (numExchange - 1)) \]

Explanation of the Formula

• numBottles: Represents the initial count of full bottles.
• (numBottles - 1) // (numExchange - 1): Represents the total number of additional bottles you can get through exchanges. Subtracting 1 from numBottles and numExchange aligns the exchange process with the available empty bottles.

By deriving this formula, we avoid the iterative process and directly calculate the maximum number of bottles that can be drunk.

Complexity

• Time Complexity: \(O(1)\) - The formula allows us to compute the result in constant time without needing iteration.
• Space Complexity: \(O(1)\) - The approach uses a constant amount of additional space regardless of the input size.

Code

C++

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        return numBottles + (numBottles - 1) / (numExchange - 1);
    }
};

Python

Java

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        return numBottles + (numBottles - 1) / (numExchange - 1);
    }
}

JavaScript

/**
 * @param {number} numBottles
 * @param {number} numExchange
 * @return {number}
 */
var numWaterBottles = function(numBottles, numExchange) {
    return numBottles + Math.floor((numBottles-1)/(numExchange-1));
};