Water Bottles

summary

• Maximum Water Bottles that can be drunk

approach

• This solution uses a greedy approach, starting with the maximum possible number of full bottles and then repeatedly exchanging empty bottles for full ones until no more exchanges are possible.

complexity

• O(n), where n is the number of full bottles

explain

• The solution starts by adding the initial number of full bottles to the total count of water bottles that can be drunk
• It then enters a loop where it repeatedly exchanges empty bottles for full ones until no more exchanges are possible
• In each iteration of the loop, it calculates the number of full bottles that can be obtained from the available empty bottles and adds this to the total count
• The number of full bottles that can be obtained in each iteration is calculated as the integer division of the number of available empty bottles by the exchange rate, plus the remainder of the division, which represents the number of empty bottles that are not enough to exchange for a full bottle.

Solution Code:

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