Water Bottles Leetcode Solution

Difficulty Level Easy
Frequently asked in Microsoft
algorithms coding Greedy Interview interviewprep LeetCode LeetCodeSolutionsViews 2877

Problem statement

In the problem ” Water Bottles” we are given two values namely” numBottle” which will store the total number of full water bottles and “numExchange” which will store the total number of empty water bottles we can exchange at a time and get a full water bottle.

After drinking water from a full water bottle it turns into an empty water bottle. Our task is to find out the maximum number of full water bottles we can drink.

Example

numBottles = 15, numExchange = 4
19

Explanation:

Water Bottles Leetcode Solution

First round: drink 15 bottles of water gives 15 empty bottles.

Second round: from these 15 water bottles we get 3 full water bottles and left with 3 empty bottles. Drink 3 water bottles we now left with a total of 6 empty bottles.

Third round: from these 6 water bottles we get 1 full water bottle and left with 2 empty bottles. Drink 1 water bottles we now left with a total of 3 empty bottles.

As a minimum of 4 bottles is required to exchange the bottle we can not buy a full water bottle anymore. So the maximum number of water bottles that we can drink is 15+3+1=19.

Approach for Water Bottles Leetcode Solution

The basic approach to solve the problem is to do what questions ask.

  1. Drink all the full water bottles then it converts to empty water bottles.
  2. From all the empty water bottles buy full water bottles.
  3. Repeat these steps until we can not buy a full water bottle from an empty water bottle.
  4. Return the total number of full water bottles that we drunk during the process.

We can improve the complexity of the solution by making a few observations:

  1. We have numBottle number of the full water bottles so this will be the minimum number of full water bottles that we can drink.
  2. 1 full water bottle = 1 unit water+1 empty water bottle.
  3. From numExchange empty water bottles, we get 1 full water bottle(1 unit water + 1 empty water bottle). This thing can also be interpreted as (numExchange-1) water bottles give 1 unit of water.
  4. But if in the last round if we have  (numExchange-1) number of empty bottles then we can not get one unit of water.
  5. So our result will be numBottle+(numBottle/(numExchange -1)) and if numBottle%(numExchange -1)==0 then subtract 1 from the final answer.

Implementation

C++ code for Water Bottles

#include <bits/stdc++.h> 
using namespace std; 
    int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
int main() 
{ 
 int numBottles = 15, numExchange = 4;
 int ans=numWaterBottles(numBottles,numExchange);
 cout<<ans<<endl;
 return 0;
}
19

Java code for Water Bottles

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
  public static void main(String[] args) {
     int numBottles = 15, numExchange = 4;
     int ans=numWaterBottles(numBottles,numExchange); 
        System.out.println(ans);
  }
}

19

Complexity Analysis of Water Bottles Leetcode Solution

Time complexity

The time complexity of the above code is O(1).

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Translate »