algoadvance

Leetcode 1518. Water Bottles

Problem Statement

You have numBottles full water bottles and you can exchange numExchange empty water bottles for one full water bottle.

The task is to write a function that returns 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.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle.

Clarifying Questions

1. What happens once I don’t have enough empty bottles to exchange for a full one?
   • You stop getting new water bottles and the process ends.
2. Is the focus purely on the count of bottles we can drink, not worrying about fractional exchanges?
   • Correct, no fractional exchanges are allowed.
3. Is this a continuous process until exchanges can’t be made?
   • Yes, you continue drinking and exchanging until it is no longer possible.
4. Are numBottles and numExchange always positive integers?
   • Yes, for the purpose of this problem, assume they are positive integers.

Strategy

To solve the problem, follow these steps:

• Initialize the total count of bottles drunk to numBottles.
• Use a loop to simulate the process of drinking and exchanging:
  • While there are enough empty bottles to perform an exchange:
    • Calculate the number of full bottles you can get by exchanging.
    • Add this number to your total count of bottles drunk.
    • Update the total number of empty bottles which will be the bottles just drank plus any remaining from previous exchanges.
• Return the total count of bottles drunk.

Code

#include <iostream>

int numWaterBottles(int numBottles, int numExchange) {
    int totalDrunk = numBottles;
    int emptyBottles = numBottles;

    while (emptyBottles >= numExchange) {
        int newBottles = emptyBottles / numExchange;
        totalDrunk += newBottles;
        emptyBottles = newBottles + (emptyBottles % numExchange);
    }

    return totalDrunk;
}

int main() {
    // Test cases
    std::cout << numWaterBottles(9, 3) << std::endl; // should output 13
    std::cout << numWaterBottles(15, 4) << std::endl; // should output 19

    return 0;
}

Time Complexity

The time complexity of this algorithm is O(log(numBottles)) because, in each iteration, the number of empty bottles is divided by at least numExchange, reducing the number of empty bottles logarithmically. This makes the approach efficient even for larger values of numBottles.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?