Leetcode 1518. Water Bottles

Problem Explanation

Here, we have a system where we start with a certain number of full water bottles (numBottles). We can drink these water bottles, converting them into empty bottles. We can also exchange a certain number of empty bottles for one full water bottle (numExchange). The task is to find out the maximum number of water bottles we can drink.

Let's look at a simple example to understand this problem better.

Say numBottles = 9 and numExchange = 3. Initially, we have 9 full water bottles. We can drink all of these, converting them into 9 empty bottles. We can then exchange these empty bottles for more full water bottles. Since each exchange requires 3 empty bottles, we can make three exchanges, netting us another 3 full water bottles. We can drink these as well and then exchange the remaining three empty bottles for one more full water bottle. So, we have a total of 9 + 3 + 1 = 13 water bottles that we can drink.

Solution Approach

The solution approach, as implemented in the solution class above, is to keep track of the total number of water bottles (ans) we have drunk so far and the current number of full water bottles (numBottles), which initially equals numBottles.

Then, as long as numBottles is greater than or equal to numExchange, we know we can make at least one exchange. We add the number of exchanges we can make to ans and update numBottles to be the number of new full water bottles we get from the exchanges (which is numBottles / numExchange) plus any leftover empty bottles that we couldn't exchange (which is numBottles % numExchange).

This process continues until numBottles is less than numExchange, at which point we can no longer make any further exchanges and thus the loop ends.

Finally, we return ans as the solution.

Now, let's look at the solutions.

Python Solution

1
2python
3class Solution:
4    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
5        ans = numBottles
6        while numBottles >= numExchange:
7            ans += numBottles // numExchange
8            numBottles = numBottles // numExchange + numBottles % numExchange
9        return ans

Java Solution

1
2java
3public class Solution {
4    public int numWaterBottles(int numBottles, int numExchange) {
5        int ans = numBottles;
6        while (numBottles >= numExchange) {
7            ans += numBottles / numExchange;
8            numBottles = numBottles / numExchange + numBottles % numExchange;
9        }
10        return ans;
11    }
12}

JavaScript Solution

1
2javascript
3class Solution {
4    numWaterBottles(numBottles, numExchange) {
5        let ans = numBottles;
6        while (numBottles >= numExchange) {
7            ans += Math.floor(numBottles / numExchange);
8            numBottles = Math.floor(numBottles / numExchange) + numBottles % numExchange;
9        }
10        return ans;
11    }
12}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int numWaterBottles(int numBottles, int numExchange) {
6        int ans = numBottles;
7        while (numBottles >= numExchange) {
8            ans += numBottles / numExchange;
9            numBottles = numBottles / numExchange + numBottles % numExchange;
10        }
11        return ans;
12    }
13};

C# Solution

1
2csharp
3public class Solution {
4    public int NumWaterBottles(int numBottles, int numExchange) {
5        int ans = numBottles;
6        while (numBottles >= numExchange) {
7            ans += numBottles / numExchange;
8            numBottles = numBottles / numExchange + numBottles % numExchange;
9        }
10        return ans;
11    }
12}

Ruby Solution

1
2ruby
3class Solution
4    def num_water_bottles(num_bottles, num_exchange)
5        ans = num_bottles
6        while num_bottles >= num_exchange
7            ans += num_bottles / num_exchange
8            num_bottles = num_bottles / num_exchange + num_bottles % num_exchange
9        end
10        return ans
11    end
12end

PHP Solution

1
2php
3class Solution {
4
5    function numWaterBottles($num_bottles, $num_exchange) {
6        $ans = $num_bottles;
7        while ($num_bottles >= $num_exchange) {
8            $ans += floor($num_bottles / $num_exchange);
9            $num_bottles = floor($num_bottles / $num_exchange) + $num_bottles % $num_exchange;
10        }
11        return $ans;
12    }
13}

Conclusion

These are the solutions to the maximum number of water bottles problem in different programming languages. The idea behind this problem is to simulate the process of drinking water bottles and exchanging the empty ones for full ones until there are not enough empty bottles left to make a full exchange. This problem can be seen as a lesson in resource management– where and how you use your resources can drastically change the output of a given program or script.

Each solution iterates over num_bottles until it's less than num_exchange. In each iteration, the number of full water bottles is updated to be the quotient of the number of full water bottles and the number of empty bottles required for one exchange, plus the remainder when the number of full water bottles is divided by the number of empty bottles required for one exchange. When num_bottles is less than num_exchange, the solution returns the total number of drinks as the result.

This way, we can keep track of the total number of drinks we can have as well as the current state of the system. We can then return this total number of drinks once there are too few full water bottles left to continue making exchanges.