1518. Water Bottles

EasyMathSimulation

Problem Description

The LeetCode problem presents a scenario where you have a specific number of full water bottles (numBottles) and a market that allows you to exchange a certain number of empty water bottles (numExchange) for one full bottle. Every time you drink a water bottle, it becomes empty, and you have the potential to use these empty bottles to get more water from the market. The challenge is to figure out the maximum number of water bottles you can drink given the initial number of bottles you have and the exchange rate at the market.

Intuition

The intuition behind the solution is to start drinking the full water bottles you have initially, keeping track of the bottles as they become empty. Every time you drink a bottle, your total count of bottles consumed increases by one. When you have enough empty bottles to exchange for a new one, you essentially 'recycle' those empty bottles, which reduces the total count of empty bottles by the exchange rate minus one (since you get one full bottle back). You then continue the process until you no longer have enough empty bottles to make an exchange.

This approach revolves around a loop where in each iteration:

You simulate the drinking process by adding the number of initial bottles to the total drunk count.
You check if you have enough empty bottles to make an exchange.
If you do, you exchange the empty ones, with the process reducing the number of empty bottles by the exchange rate minus one, adding one new full bottle to the total count, and then proceeding to drink again.
This continues until you don't have enough empty bottles to exchange for a new one.

The solution is a greedy approach whereby at each step, you consume as many bottles as possible and exchange as soon as possible, thereby guaranteeing the maximum drinking count.

Learn more about Math patterns.

Solution Approach

The implementation of the solution uses a while loop to simulate the drinking and exchanging process until it's not possible to exchange empty bottles for a full one.

Initially, we set ans to numBottles since we can drink all those bottles at the very least. We then enter a loop that continues as long as numBottles is greater than or equal to numExchange. This condition checks whether we have enough empty bottles to make an exchange for a full one.

During each iteration of the loop:

We simulate exchanging empty bottles for a full one by reducing numBottles by numExchange - 1. We subtract one less than numExchange because we are effectively giving away numExchange bottles and receiving one full bottle in return, resulting in a net loss of numExchange - 1 empty bottles.
We increment the answer (ans) by 1 to account for the new full bottle we obtained from the exchange, which we assume we drink immediately.

When it's no longer possible to exchange (i.e., when numBottles is less than numExchange), we exit the loop and the total ans represents the maximum number of bottles we could have drunk.

The algorithm uses constant space, as we only need a few integer variables to keep track of the bottles consumed and the bottles remaining, and the time complexity is O(n), where n is the initial number of bottles because we decrease numBottles by at least one in each iteration of the loop.

Overall, the solution counts the total number of bottles drunk by incrementally exchanging empty bottles for full ones until we can make no more exchanges, adding up the initial full bottles and the extra ones gained through exchange.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Say we have numBottles = 9 full water bottles and the market allows us to exchange numExchange = 3 empty bottles for 1 full bottle.

Initially, we can drink all 9 bottles, so ans initially becomes 9. Each time we drink a bottle, it becomes empty. After drinking these, we have 9 empty bottles.

Now, we can exchange these 9 empty bottles for 9/3 = 3 full bottles. After drinking these 3 bottles, our total ans is now 9 (initially drunk) + 3 (newly drunk) = 12.

Again, we have 3 empty bottles from the ones we just consumed, so we can exchange these 3 empty bottles for 1 full bottle. After drinking this one as well, our ans is 12 + 1 = 13.

Now we have only 1 empty bottle left, and because we have fewer empty bottles than numExchange, we can't exchange them for more full bottles.

Therefore, the maximum number of water bottles we can drink is 13.

In this example, the while loop runs each time we have enough empty bottles to exchange for a new full bottle. Each time, we add to our total count of drunk bottles and reduce the number of empty bottles according to the exchange rate. This process of drinking and exchanging continues until we can no longer exchange the empties for a full one, and we obtain our ans.

Solution Implementation

1class Solution:
2    def numWaterBottles(self, num_bottles: int, num_exchange: int) -> int:
3        # Total amount of drinkable bottles is initially the same as the number of bottles.
4        total_drinkable_bottles = num_bottles
5      
6        # Continue the loop as long as we have enough bottles to exchange for a new one.
7        while num_bottles >= num_exchange:
8            # Calculate the remaining bottles after performing an exchange.
9            # The number of empty bottles to exchange is reduced by 'num_exchange',
10            # but we get one new bottle in return, hence the '-1'.
11            num_bottles = num_bottles - num_exchange + 1
12          
13            # Update the total number of drinkable bottles after the exchange.
14            total_drinkable_bottles += 1
15      
16        # Return the total number of drinkable bottles we can have.
17        return total_drinkable_bottles
18

1class Solution {
2    public int numWaterBottles(int numBottles, int numExchange) {
3        // Initialize totalDrunkBottles with the number of bottles we start with
4        int totalDrunkBottles = numBottles;
5      
6        // Continue the process as long as we have enough empty bottles to exchange
7        while (numBottles >= numExchange) {
8            // Calculate the number of new bottles we can get by exchanging
9            int newBottles = numBottles / numExchange;
10          
11            // Update the count of total drunk bottles with the new bottles
12            totalDrunkBottles += newBottles;
13          
14            // Update the current number of bottles we have,
15            // Including the new bottles and the bottles left after the exchange
16            numBottles = newBottles + (numBottles % numExchange);
17        }
18      
19        // Return the total number of drunk bottles
20        return totalDrunkBottles;
21    }
22}
23

1class Solution {
2public:
3    // The function calculates the total number of water bottles one can drink,
4    // given the initial number of bottles and the number of empty bottles required
5    // to exchange for a new full water bottle.
6    int numWaterBottles(int numBottles, int numExchange) {
7        int totalDrunk = numBottles; // Total bottles drunk includes initial bottles
8        while (numBottles >= numExchange) {
9            // Each time the loop runs, we can exchange 'numExchange' empty bottles
10            // for one new full bottle. In the process, we effectively lose
11            // 'numExchange - 1' empty bottles since we get one full bottle back.
12            numBottles -= (numExchange - 1);
13
14            // Increment the total drunk since we gained one bottle by exchanging
15            totalDrunk++;
16
17            // No change in amount of code here, but using loop condition for clarity
18        }
19        return totalDrunk;
20    }
21};
22

1// This function calculates the total number of water bottles one can drink
2// given the number of initial bottles and the number of empty bottles
3// required for exchanging them for a new one.
4function numWaterBottles(initialBottles: number, exchangeRate: number): number {
5    // The total number of water bottles one can drink.
6    let totalDrinks = initialBottles;
7  
8    // Keep exchanging the bottles until there are not enough to exchange for a new one.
9    while (initialBottles >= exchangeRate) {
10        // Calculate the number of new bottles earned through exchange.
11        const newBottles = Math.floor(initialBottles / exchangeRate);
12      
13        // Update total drinks with the new bottles obtained.
14        totalDrinks += newBottles;
15      
16        // Update the count of bottles: bottles left after exchange + new bottles.
17        initialBottles = newBottles + (initialBottles % exchangeRate);
18    }
19  
20    return totalDrinks;
21}
22

Time and Space Complexity

Time Complexity

The time complexity of the given code can be represented as O(n), where n represents the initial number of bottles. This is because with each iteration we effectively simulate drinking a bottle of water and then exchanging the empty bottles for a full one. The loop continues until the number of bottles is less than numExchange, which happens after n / (numExchange - 1) iterations, where integer division is implied.

Space Complexity

The space complexity of the code is O(1) as there are only a few integer variables allocated (ans, numBottles, numExchange), and no additional data structures that grow with the size of the input are used. The amount of memory used is constant regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know