Blogs Hub

by Sumit Chourasia | Oct 05, 2020 | Category :coding | Tags : algorithm data-structure easy greedy leetcode

Water Bottles - Greedy - Easy - LeetCode

Water Bottles - Greedy - Easy - LeetCode

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

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

Return the maximum number of water bottles you can drink.

 

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.
Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6
Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2
 

Constraints:

1 <= numBottles <= 100
2 <= numExchange <= 100

public class Solution {
    public int NumWaterBottles(int numBottles, int numExchange) {
        int total = 0;
        int spare = 0;
        while(numBottles>0){
            total += numBottles;
            numBottles += spare;            
            spare = numBottles%numExchange;
            numBottles = numBottles/numExchange;
        }
        
        return total;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)