Water Bottles - LeetCode 1518 - Beats 100%

In this blog post, we'll explore a fun and practical problem: determining the maximum number of water bottles you can drink given a certain number of initial full water bottles and the ability to exchange a set number of empty bottles for new full ones.

Let's dive into the problem and its solution using C++.

Problem Statement

You are given two integers:

• numBottles: The number of full water bottles you start with.

• numExchange: The number of empty water bottles you need to exchange for one full bottle.

Every time you drink a full water bottle, it turns into an empty bottle. The goal is to calculate the maximum number of water bottles you can drink by continually exchanging empty bottles for full ones.

Solution Approach

To solve this problem, we simulate the process of drinking water and exchanging empty bottles. Here's the plan:

1. Start with the total number of drinks equal to the initial number of full bottles.

2. Track the number of empty bottles.

3. While the number of empty bottles is greater than or equal to the exchange rate, continue exchanging empty bottles for new full bottles and keep drinking.

4. Update the total number of drinks and the count of empty bottles after each exchange

5. Return the total number of drinks once no more exchanges can be made.

#include <iostream>
using namespace std;

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int total_drinks = numBottles;
        int empty_bottles = numBottles;

        while (empty_bottles >= numExchange) {
            int new_bottles = empty_bottles / numExchange;
            total_drinks += new_bottles;
            empty_bottles = empty_bottles % numExchange + new_bottles;
        }

        return total_drinks;
    }
};

// Driver code
int main() {
    Solution test;
    cout << test.numWaterBottles(9, 3);
    return 0;
}

How It Works

1. Initialization:

   1. We initialize total_drinks with the initial number of full bottles numBottles.

   2. We also initialize empty_bottles with the same value because once we drink the full bottles, they become empty.

2. Exchange Loop:

   1. We use a while loop to continuously exchange empty bottles for new full bottles as long as the number of empty bottles is greater than or equal to numExchange.

   2. Inside the loop, we calculate new_bottles as the integer division of empty_bottles by numExchange.

   3. We add the new_bottles to total_drinks.

   4. We update empty_bottles to be the remainder of the empty bottles after the exchange (empty_bottles % numExchange) plus the new bottles obtained from the exchange.

3. Result:

   Once the loop exits (when we no longer have enough empty bottles to exchange for a new full bottle), we return total_drinks which contains the total number of bottles consumed.

Example

Consider the example where numBottles = 9 and numExchange = 3:

• Initially, you have 9 full bottles.

• You drink 9 bottles, which leaves you with 9 empty bottles.

• You exchange 9 empty bottles for 3 full bottles (3 exchanges of 3 empty bottles).

• You drink the 3 new full bottles, leaving you with 3 empty bottles.

• You exchange the 3 empty bottles for 1 full bottle (1 exchange of 3 empty bottles).

• You drink the 1 full bottle, leaving you with 1 empty bottle.

• You cannot exchange 1 empty bottle for a new full bottle, so the process stops.

• Total drinks = 9 (initial) + 3 (first exchange) + 1 (second exchange) = 13.

This algorithm ensures that all possible exchanges are made, and the total number of drinks is maximized.

Conclusion

By simulating the process of drinking and exchanging bottles, we can effectively determine the maximum number of water bottles one can consume. This solution demonstrates the power of simple loops and arithmetic operations in solving real-world problems.

Feel free to try out the code with different values of numBottles and numExchange to see how many bottles you can drink! Happy coding!