Maximum Number of Bottles You Can Drink Using a Greedy Algorithm

The article introduces a marketing promotion where customers can exchange a certain number of empty wine bottles for a new bottle, describing the rules: buying X bottles allows Y empty bottles to be exchanged for one new bottle, with Y chosen randomly.

It then asks the reader to compute the maximum number of bottles that can be consumed, providing four examples with specific X and Y values and their corresponding results.

To solve the problem, the author identifies two challenges: the exchange ratio Y is random, and exchanged bottles can be reused for further exchanges. The solution uses a greedy algorithm that always exchanges whenever possible, ensuring the global optimum.

The article explains the greedy algorithm concept, its suitability for problems with optimal substructure, and presents a generic greedy framework.

Greedy Algorithm Implementation 1

The first implementation repeatedly exchanges one bottle at a time using addition and subtraction:

// Greedy 1: using + and -
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // maximum number of bottles
        int total = numBottles;
        // exchange while possible
        while (numBottles >= numExchange) {
            // perform one exchange
            numBottles -= numExchange;
            ++total;
            // after drinking the new bottle, we get an extra empty bottle
            ++numBottles;
        }
        return total;
    }
}

The code first counts the initial bottles, then loops while enough empty bottles exist, performing an exchange, incrementing the total count, and adding the newly emptied bottle back to the pool.

Greedy Algorithm Implementation 2 (Optimized)

The second version maximizes each exchange round by using division and modulo operations:

// Greedy 2: using / and %
class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        // total bottles
        int total = numBottles;
        // exchange while possible
        while (numBottles >= numExchange) {
            // maximum new bottles obtainable this round
            int n = numBottles / numExchange;
            // accumulate total
            total += n;
            // remaining bottles = leftover + newly emptied bottles
            numBottles = numBottles % numExchange + n;
        }
        return total;
    }
}

This version computes how many new bottles can be obtained in one step, adds them to the total, and updates the count of empty bottles using the remainder plus the newly drunk bottles.

Both implementations were submitted to LeetCode and produced the expected results for the sample test cases.

In conclusion, the greedy approach, though seemingly complex, is straightforward to implement and illustrates how algorithmic thinking can simplify real‑world promotional problems.