Skip to main content

Water Bottles Solution

In this page, we will solve the Water Bottles problem using different approaches: iterative simulation and a more optimized approach. We will provide the implementation of the solution in Python, Java, C++, JavaScript, and more.

Problem Description

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

Examples

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Constraints

  • 1<=numBottles<=1001 <= numBottles <= 100
  • 2<=numExchange<=1002 <= numExchange <= 100

Solution for Water Bottles Problem

Intuition and Approach

The problem can be solved by simulating the process of drinking water bottles and exchanging empty ones for full ones until no more exchanges can be made.

Approach 1: Iterative Simulation

We iteratively drink the water bottles and exchange the empty ones until no more exchanges are possible.

Implementation

Live Editor
function maxBottles() {
  const numBottles = 9;
  const numExchange = 3;

  const maxWaterBottles = function(numBottles, numExchange) {
    let totalDrank = numBottles;
    let emptyBottles = numBottles;

    while (emptyBottles >= numExchange) {
      const newBottles = Math.floor(emptyBottles / numExchange);
      totalDrank += newBottles;
      emptyBottles = emptyBottles % numExchange + newBottles;
    }

    return totalDrank;
  };

  const result = maxWaterBottles(numBottles, numExchange);
  return (
    <div>
      <p>
        <b>Input:</b> numBottles = {numBottles}, numExchange = {numExchange}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Code in Different Languages

Written by @manishh12
 function maxWaterBottles(numBottles, numExchange) {
let totalDrank = numBottles;
let emptyBottles = numBottles;

while (emptyBottles >= numExchange) {
const newBottles = Math.floor(emptyBottles / numExchange);
totalDrank += newBottles;
emptyBottles = emptyBottles % numExchange + newBottles;
}

return totalDrank;
}

Complexity Analysis

  • Time Complexity: O(logn)O(\log n), where n is the initial number of bottles, due to the iterative division.
  • Space Complexity: O(1)O(1), as we are using a constant amount of extra space.
Note

By using both iterative simulation and an optimized mathematical approach, we can efficiently solve the Water Bottles problem. The choice between the two approaches depends on the specific requirements and constraints of the problem.

References