Minimum Cost of Buying Candies With Discount

Minimum Cost of Buying Candies With Discount

What is this problem about?

The Minimum Cost of Buying Candies With Discount problem involves a shop where for every two candies you buy, you get one candy for free. The catch is that the free candy must have a cost less than or equal to the minimum of the two candies you just purchased. You are given an array of candy costs and need to find the minimum total cost to acquire all the candies in the shop.

Why is this asked in interviews?

This is a standard Minimum Cost of Buying Candies interview question for entry-level roles at companies like Garmin and Amazon. It tests a candidate's ability to apply a Greedy strategy to maximize savings. It evaluates if you can identify that you should always use the "free" slot for the most expensive candy possible that satisfies the condition.

Algorithmic pattern used

The Greedy interview pattern with Sorting is perfect here.

1. Sort the candy costs in descending order.
2. Group the candies in triplets.
3. In each triplet, you pay for the first two (the most expensive) and get the third one for free.
4. Sum up the costs of all candies except every third one in the sorted list.

Example explanation

Candy costs: [6, 5, 2, 2, 8, 2].

1. Sort descending: [8, 6, 5, 2, 2, 2].
2. First triplet: Buy 8 and 6, get 5 for free. (Cost: 14)
3. Second triplet: Buy 2 and 2, get 2 for free. (Cost: 4)
4. Total minimum cost = 14 + 4 = 18. If you had paired them differently, you might have gotten a cheaper candy (like 2) for free, which wouldn't be as efficient.

Common mistakes candidates make

• Not sorting descending: Trying to pair candies from the start or at random, which doesn't maximize the value of the "free" candy.
• Sorting ascending: If you sort [2, 2, 2, 5, 6, 8] and take every third, you get the smallest ones for free, which is the opposite of what you want.
• Miscounting the groups: Not handling the remaining 1 or 2 candies correctly if the total count is not a multiple of 3.

Interview preparation tip

Whenever you have a "buy X get Y free" problem, Greedy with Sorting is almost always the answer. To minimize the cost, you want to get the most expensive possible items for free. Sorting descending allows you to sacrifice the top two costs to get the third-highest cost for free.