Problem Statement

There are numBottles number of bottles filled with water. You can trade a numExchange number of empty bottles and get a single filled water bottle.

When you drink a bottle, it becomes empty.

Given the two integers numBottles and numExchange, return the maximum number of water bottles you can drink.

Examples

Example 1

• Input: numBottles = 15, numExchange = 4
• Expected Output: 19
• Explanation:
  • You start with 15 full bottles.
  • Drink 15 bottles (now 15 empty).
  • Exchange 12 empty bottles for 3 full (now 3 full, 3 empty).
  • Drink 3 more (now 6 empty).
  • Exchange 4 empty for 1 full (now 1 full, 2 empty).
  • Drink 1 more (now 3 empty).
  • You can't get 1 full bottle using 3 empty bottles.
  • You can drink 15 + 3 + 1 = 19 bottoles.

Example 2

• Input: numBottles = 7, numExchange = 3
• Expected Output: 10
• Explanation:
  • Start with 7 full bottles.
  • Drink 7 bottles (7 empty).
  • Exchange 6 empty for 2 full (now 2 full, 1 empty).
  • Drink 2 more (3 empty).
  • Exchange 3 empty for 1 full (now 1 full, 0 empty).
  • Drink 1 more (total = 7 + 2 + 1 = 10).

Example 3

• Input: numBottles = 5, numExchange = 5
• Expected Output: 6
• Explanation:
  • Start with 5 full bottles.
  • Drink 5 bottles (5 empty).
  • Exchange 5 empty for 1 full (now 1 full, 0 empty).
  • Drink 1 more (total = 5 + 1 = 6).

Constraints:

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

Solution

To solve this problem, we need to maximize the number of water bottles we can drink by making use of the exchange system for empty bottles. We start by drinking numExchange number of water bottles in 1 move and exchange it with 1 full bottle. We continue this process until we no longer have enough empty bottles to exchange for a full one. This approach works because it allows us to maximize the number of full bottles we can drink by continuously converting empty bottles back into full ones as long as possible.

Step-by-step Algorithm

1. Initialize totalDrunkBottles to 0:

   • We start with totalDrunkBottles = 0 to keep a count of all the bottles we drink during the process.

2. While loop (numBottles >= numExchange):

   • This loop ensures that as long as we have enough bottles to exchange for at least one full bottle, we continue the process.

3. Inside the Loop: Drink and Exchange

   • Add numExchange to totalDrunkBottles:
     • In each iteration, we drink as many bottles as we can exchange in that round, so we add numExchange to totalDrunkBottles.
   • Subtract numExchange from numBottles:
     • After drinking numExchange bottles, we subtract this number from numBottles because those bottles are now empty.
   • Increment numBottles by 1:
     • After subtracting numExchange, we simulate exchanging the empty bottles to get one full bottle back, thus incrementing numBottles by 1.

4. Add Remaining Bottles to totalDrunkBottles:

   • Once the loop exits (when numBottles < numExchange), we add any remaining bottles to totalDrunkBottles because these are the bottles we can still drink but cannot exchange for more.

5. Return totalDrunkBottles.

Algorithm Walkthrough

Input: numBottles = 15, numExchange = 4

1. Initialize totalDrunkBottles to 0.

2. Start with 15 full bottles:

   • Iteration 1:
     • Drink 4 bottles: totalDrunkBottles = 4, numBottles = 11 (15 - 4)
     • Exchange 4 empty bottles for 1 full bottle: numBottles = 12 (11 + 1)
   • Iteration 2:
     • Drink 4 bottles: totalDrunkBottles = 8, numBottles = 8 (12 - 4)
     • Exchange 4 empty bottles for 1 full bottle: numBottles = 9 (8 + 1)
   • Iteration 3:
     • Drink 4 bottles: totalDrunkBottles = 12, numBottles = 5 (9 - 4)
     • Exchange 4 empty bottles for 1 full bottle: numBottles = 6 (5 + 1)
   • Iteration 4:
     • Drink 4 bottles: totalDrunkBottles = 16, numBottles = 2 (6 - 4)
     • Exchange 4 empty bottles for 1 full bottle: numBottles = 3 (2 + 1)

3. Add remaining bottles to totalDrunkBottles: totalDrunkBottles = 19 (16 + 3)

4. Return totalDrunkBottles: 19

Code

Complexity Analysis

Time Complexity: O(numBottles)

The maximum number of operations in the while loop occurs when the value of numExchange is 2. In this case, for each iteration, the number of full bottles decreases by 1 (as 2 full bottles are exchanged for 1 new full bottle). Thus, the overall time complexity of the algorithm is O(numBottles).

Space Complexity: O(1)

The space complexity is O(1) since we are using a constant amount of extra space for variables (totalDrunkBottles and numBottles).

An Alternate Approach (Optimized Simulation)

In this approach, we keep track of the total number of bottles consumed and repeatedly exchange empty bottles for new full ones until no more exchanges can be made. The process involves drinking all available full bottles, collecting the empty ones, and then trading them for new full bottles if possible. This approach ensures that every possible bottle exchange is utilized, thus maximizing the number of bottles consumed.

Step-by-Step Algorithm

1. Initialize Variables:

   • Start with consumedBottles = 0 to keep track of the total number of bottles drunk.

2. Loop to Calculate and Perform Exchanges:

   • While numBottles >= numExchange:
     • Continue as long as we have enough bottles to exchange for a new full bottle.

3. Calculate Maximum Number of Exchanges:

   • Compute K = numBottles / numExchange:
     • This gives the maximum number of exchanges possible with the current full bottles.

4. Update Consumed Bottles and Remaining Full Bottles:

   • Add numExchange * K to consumedBottles:
     • Count the bottles consumed from these exchanges.
   • Subtract numExchange * K from numBottles:
     • Update the number of full bottles after the exchanges.
   • Add K to numBottles:
     • Include the new full bottles obtained from the exchanges.

5. Add Remaining Bottles:

   • Return consumedBottles + numBottles:
     • Include any remaining full bottles that are less than numExchange.

Algorithm Walkthrough

Input: numBottles = 15, numExchange = 4

1. Initial State:

   • numBottles = 15
   • consumedBottles = 0

2. First Iteration:

   • Calculate the number of exchanges possible: K = 15 / 4 = 3
   • Add the consumed bottles: consumedBottles = 0 + 4 * 3 = 12
   • Subtract the used bottles: numBottles = 15 - 4 * 3 = 3
   • Add the new full bottles: numBottles = 3 + 3 = 6

3. Second Iteration:

   • Calculate the number of exchanges possible: K = 6 / 4 = 1
   • Add the consumed bottles: consumedBottles = 12 + 4 * 1 = 16
   • Subtract the used bottles: numBottles = 6 - 4 * 1 = 2
   • Add the new full bottles: numBottles = 2 + 1 = 3

4. Exit Loop:

   • Now numBottles = 3, which is less than numExchange = 4, so exit the loop.

5. Final Addition:

   • Add the remaining bottles: consumedBottles = 16 + 3 = 19

6. Return Result:

   • Return consumedBottles = 19

Code

Complexity Analysis

• Time Complexity: The time complexity of the algorithm is O(\log_{\text{numExchange}}(\text{numBottles})). This is because in each iteration of the while loop, the number of bottles decreases by a factor of approximately \text{numExchange}. Thus, the number of iterations is logarithmic with respect to the number of bottles.

• Space Complexity: The space complexity is O(1). The algorithm uses a constant amount of extra space regardless of the input size.