Domain 1EasyCORE

Water Bottles

The problem asks us to determine the maximum number of water bottles that can be drunk given an initial number of full water bottles (`numBottles`) and a rule for exchanging empty bottles for full ones (`numExchange`). Each time we drink a bottle, it turns into an empty bottle. The goal is to maximize the number of drinks by continuously exchanging empty bottles for full ones until no more exchanges can be made.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy

1518. Water Bottles

Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 0
Acceptance rate: 60.6%


Problem Breakdown

The problem asks us to determine the maximum number of water bottles that can be drunk given an initial number of full water bottles (numBottles) and a rule for exchanging empty bottles for full ones (numExchange). Each time we drink a bottle, it turns into an empty bottle. The goal is to maximize the number of drinks by continuously exchanging empty bottles for full ones until no more exchanges can be made.

Inputs:

  • numBottles: An integer representing the initial number of full water bottles.
  • numExchange: An integer representing how many empty bottles are needed to exchange for one full bottle.

Outputs:

  • An integer representing the maximum number of water bottles that can be drunk.

Implicit Constraints:

  • The number of bottles and exchanges are within reasonable limits (1 <= numBottles <= 100, 2 <= numExchange <= 100).
  • Edge cases include scenarios where:
    • numBottles is less than numExchange, meaning no exchanges can be made.
    • numBottles equals numExchange, allowing exactly one exchange.

Intuition

A brute-force approach would involve simulating the drinking and exchanging process iteratively until no more exchanges can be made. However, this could lead to inefficient code with high time complexity, especially if many iterations are needed.

The key insight is to recognize that each cycle of drinking and exchanging can be modeled mathematically. Specifically, we can calculate how many full bottles can be obtained from the initial empty bottles after a certain number of drinks, and then use this information to determine when no more exchanges can be made.

Approach

  1. Initialize Variables:

    • totalDrinks to keep track of the total number of bottles drunk.
    • emptyBottles to keep track of the current number of empty bottles, initially set to numBottles.
  2. Iterate Until No More Exchanges Can Be Made:

    • While emptyBottles is greater than or equal to numExchange:
      • Calculate the number of new full bottles that can be obtained by integer division (emptyBottles // numExchange).
      • Update totalDrinks by adding the newly obtained full bottles.
      • Update emptyBottles to account for the new empty bottles from drinking and the remaining empty bottles after exchange.
  3. Return the Total Number of Drinks:

Complexity Analysis

  • Time Complexity: O(log(numBottles)) because in each iteration, the number of empty bottles is reduced by a factor related to numExchange.
  • Space Complexity: O(1) since we are using a constant amount of extra space.

Solution

def numWaterBottles(numBottles: int, numExchange: int) -> int:
    totalDrinks = 0
    emptyBottles = numBottles
    
    while emptyBottles >= numExchange:
        newFullBottles = emptyBottles // numExchange
        totalDrinks += newFullBottles
        emptyBottles = newFullBottles + (emptyBottles % numExchange)
    
    return totalDrinks + numBottles

Edge Cases Handled

  • Edge Case 1: numBottles is less than numExchange.

    • The loop condition ensures that no exchanges are made, and the function returns just the initial number of bottles.
  • Edge Case 2: numBottles equals numExchange.

    • One exchange can be made, resulting in a total of numBottles + 1 drinks.
  • General Edge Cases:

    • The algorithm handles cases where multiple exchanges are possible and ensures that all potential full bottles from exchanges are counted.