LeetCode 1518. Water Bottles

Description

https://leetcode.com/problems/water-bottles/

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

Explanation

The key idea is to simulate the process, find out what are the steps in one iteration and what’s the condition to loop the iteration. Base on the example picture, we can consider 1. drinking bottles to empty bottles 2. exchange empty bottles for new bottles as steps in one iteration. Then when bottles + empty bottles are greater than the minimum exchange number, we loop the process.

Python Solution

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:        
        count = 0
        
        empty_bottles = 0
        while numBottles + empty_bottles >= numExchange:
            count += numBottles 
            empty_bottles += numBottles
            numBottles = empty_bottles // numExchange
            empty_bottles = empty_bottles % numExchange
            
        
        count += numBottles 
               
        return count
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.