We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Water Bottles

Number: 1642

Difficulty: Easy

Paid? No

Companies: Amazon, HiLabs, Accenture, Google, Microsoft

Problem Description

You are given numBottles full water bottles and can exchange numExchange empty bottles for one full water bottle. Each time you drink a full bottle, it becomes empty. The goal is to calculate the maximum number of water bottles you can drink by continuously exchanging empty bottles for full ones until you cannot make any more exchanges.

Key Insights

  • The simulation proceeds by drinking the bottles, which turns them into empties.
  • Use the number of empty bottles to determine how many exchanges can be done.
  • Each exchange provides additional full bottles that, when drunk, yield more empties, which could lead to further exchanges.
  • The process stops when the number of empty bottles is less than numExchange.

Space and Time Complexity

Time Complexity: O(n) in the worst case, but given small constraints, the simulation loop will run a limited number of times. Space Complexity: O(1), as only a few variables are used.

Solution

We solve the problem by simulating the process of drinking and exchanging. Start with the initial full bottles (numBottles) and treat that number as the initial count of empty bottles after drinking them. In each iteration, calculate how many new full bottles can be obtained by exchanging the current empties, add those to the total count of bottles consumed, and update the empty bottle count. Use a while loop that continues as long as the empty bottle count meets or exceeds the exchange threshold. The key data structures are simple integer counters. This simulation-based approach ensures we correctly account for every exchange until it is no longer possible.

Code Solutions

# Function to compute the maximum number of water bottles that can be drunk
def maxWaterBottles(numBottles: int, numExchange: int) -> int:
    # Initialize the total bottles drunk with the initial full bottles
    total_drunk = numBottles
    # Initially, all full bottles turn into empty bottles after drinking
    empty_bottles = numBottles
    
    # Continue exchanging as long as there are enough empty bottles
    while empty_bottles >= numExchange:
        # Calculate how many new full bottles can be obtained via exchange
        new_full = empty_bottles // numExchange
        # Increase the total count by the newly obtained full bottles
        total_drunk += new_full
        # Update the count of empty bottles:
        # remaining empty bottles after exchange + bottles just consumed become empty
        empty_bottles = (empty_bottles % numExchange) + new_full
        
    return total_drunk

# Example usage:
print(maxWaterBottles(9, 3))  # Expected output: 13
← Back to All Questions