1518. Water Bottles.md

1518. Water Bottles

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.

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 <= 100
• 2 <= numExchange <= 100

---

Solution

Given the two integers numBottles and numExchange where numExchange denotes the number of empty bottles that can be exchanged to get a full bottle, return the maximum number of water bottles you can drink.

Approach

This is a simple implementational problem where we can count the maximum number of water bottles that we can drink from the available full water bottles and the number of empty bottles that can be exchanged unitl it is not possible to exchange any empty bottle.

Algorithm

1. Declare result = 0 & result = 0
2. While numBottles is not empty, loop:
   • result = result + numBottles
   • curEmptyBottles = prevEmptyBottles + numBottles
   • numBottles = curEmptyBottles / numExchange
   • prevEmptyBottles = curEmptyBottles % numExchange
3. Return result

Explanation with example

Input: numBottles = 9, numExchange = 3
Output: 13

numBottles	numExchange	result	curEmptyBottles	Updated numBottles	prevEmptyBottles
9	3	9	9	3	0
3	3	12	3	1	0
1	3	13	1	0	1

Result is 13.

Complexity

• Time Complexity:

  • O(log(numBottles)

• Space Complexity:

  • O(1)

Code

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int result = 0;
        int prevEmptyBottles = 0;
        while(numBottles) {
            result += numBottles;
            int curEmptyBottles = prevEmptyBottles + numBottles;
            numBottles = curEmptyBottles/numExchange;
            prevEmptyBottles = curEmptyBottles%numExchange;
        }
        return result;
    }
};

Tags: C++, cpp, leetcode, leetcode 1518, Greedy, Implementation