Minimum Cost of Buying Candies With Discount
Problem
For every two candies you buy, the shop gives a third candy free, as long as the free candy costs no more than the cheaper of the two you bought. Given an array cost of candy prices, return the minimum total cost to buy all candies.
Greedy insight: sort prices high to low and process them in triples. In each triple you pay for the two most expensive candies and take the third (the cheapest of the trio) for free, so the free candies are the ones at sorted positions 2, 5, 8, …
cost = [6,5,7,9,2,2]23def minimumCost(cost):
cost.sort(reverse=True) # most expensive first
total = 0
for i in range(len(cost)):
if i % 3 == 2: # every third candy is free
continue
total += cost[i] # pay for this candy
return totalfunction minimumCost(cost) {
cost.sort((a, b) => b - a); // most expensive first
let total = 0;
for (let i = 0; i < cost.length; i++) {
if (i % 3 === 2) continue; // every third candy is free
total += cost[i]; // pay for this candy
}
return total;
}int minimumCost(int[] cost) {
Integer[] c = new Integer[cost.length];
for (int i = 0; i < cost.length; i++) c[i] = cost[i];
Arrays.sort(c, Collections.reverseOrder()); // high to low
int total = 0;
for (int i = 0; i < c.length; i++) {
if (i % 3 == 2) continue; // every third candy is free
total += c[i]; // pay for this candy
}
return total;
}int minimumCost(vector<int>& cost) {
sort(cost.rbegin(), cost.rend()); // most expensive first
int total = 0;
for (int i = 0; i < (int)cost.size(); i++) {
if (i % 3 == 2) continue; // every third candy is free
total += cost[i]; // pay for this candy
}
return total;
}Explanation
This is a classic greedy problem. The discount lets us pick one free candy for every two we buy, but the free candy must cost no more than the cheaper of the two purchased. To make the most of every discount, we want the candies we get for free to be as expensive as the rule allows.
The key move is to sort the prices in descending order. Then we look at the array in consecutive groups of three. Inside each group the first two entries are the two most expensive remaining candies — we pay for them — and the third entry is automatically the cheapest of that trio, so it is always a legal free candy.
Concretely, after sorting we add every price to the total except the ones whose index is 2, 5, 8, … — that is, the positions where i % 3 == 2. Those skipped candies are exactly the ones taken for free, and because the array is sorted descending, each freebie is the most expensive candy we were allowed to grab at that step.
Why is this optimal? Any valid plan gives away at most one candy per two purchases. Pairing the largest leftover prices to "unlock" the next-largest as free maximizes the discount at every step, and a simple exchange argument shows no other pairing can save more.
Example: cost = [6,5,7,9,2,2] sorts to [9,7,6,5,2,2]. We pay 9 and 7 and take 6 free, then pay 5 and 2 and take the last 2 free. Total paid = 9 + 7 + 5 + 2 = 23.