Water Bottles II

medium math simulation greedy

Problem

You start with numBottles full water bottles. Each turn you may drink any number of full bottles (each becomes empty), or exchange numExchange empty bottles for one full bottle — and right after that exchange numExchange increases by one. You can never reuse the same numExchange price for two batches. Return the maximum number of water bottles you can drink.

InputnumBottles = 13, numExchange = 6

Output15

Drink 13. Exchange 6 empties (price→7) for 1, drink it (14). Exchange 7 empties (price→8) for 1, drink it (15). Now only 2 empties remain, less than 8, so stop.

numBottles

numExchange

def maxBottlesDrunk(numBottles, numExchange):
    drunk = numBottles            # drink every full bottle right away
    empty = numBottles            # each one drunk becomes an empty
    while empty >= numExchange:    # can we still afford an exchange?
        empty -= numExchange      # hand over numExchange empties
        numExchange += 1          # the price goes up by one
        drunk += 1                # we get one full bottle and drink it
        empty += 1                # that bottle is now empty too
    return drunk                  # no exchange possible -> answer

function maxBottlesDrunk(numBottles, numExchange) {
  let drunk = numBottles;          // drink every full bottle right away
  let empty = numBottles;          // each one drunk becomes an empty
  while (empty >= numExchange) {    // can we still afford an exchange?
    empty -= numExchange;          // hand over numExchange empties
    numExchange += 1;              // the price goes up by one
    drunk += 1;                    // we get one full bottle and drink it
    empty += 1;                    // that bottle is now empty too
  }
  return drunk;                    // no exchange possible -> answer
}

int maxBottlesDrunk(int numBottles, int numExchange) {
    int drunk = numBottles;          // drink every full bottle right away
    int empty = numBottles;          // each one drunk becomes an empty
    while (empty >= numExchange) {    // can we still afford an exchange?
        empty -= numExchange;        // hand over numExchange empties
        numExchange += 1;            // the price goes up by one
        drunk += 1;                  // we get one full bottle and drink it
        empty += 1;                  // that bottle is now empty too
    }
    return drunk;                    // no exchange possible -> answer
}

int maxBottlesDrunk(int numBottles, int numExchange) {
    int drunk = numBottles;          // drink every full bottle right away
    int empty = numBottles;          // each one drunk becomes an empty
    while (empty >= numExchange) {    // can we still afford an exchange?
        empty -= numExchange;        // hand over numExchange empties
        numExchange += 1;            // the price goes up by one
        drunk += 1;                  // we get one full bottle and drink it
        empty += 1;                  // that bottle is now empty too
    }
    return drunk;                    // no exchange possible -> answer
}

Explanation

This is a direct simulation. We never need to be clever about which bottles to drink — drinking is free and only ever helps, so the very first move is to drink all numBottles full bottles. That gives us a starting count of empties equal to numBottles.

From there the only meaningful action is exchanging. As long as we hold at least numExchange empty bottles we can trade exactly numExchange of them for one full bottle. We immediately drink that bottle, so it adds one to drunk and one back to empty.

The twist that makes this II: every exchange raises the price. So after spending numExchange empties we do numExchange += 1. Each batch is strictly more expensive than the last, which is why the loop must terminate — the cost grows by one every round while the supply of empties shrinks.

Net effect of one exchange on the empty count: we remove numExchange empties and add back 1 (the bottle we just drank). The loop keeps running while empty >= numExchange and stops the moment we can no longer afford the next, rising price.

Example: numBottles = 13, numExchange = 6. Drink 13 (empty = 13). Pay 6 (empty = 7, price = 7), drink 1 → 14, empty = 8. Pay 7 (empty = 1, price = 8), drink 1 → 15, empty = 2. Now 2 < 8, so we stop with the answer 15.

Time: O(√numBottles) Space: O(1)