Minimum Cost of Buying Candies With Discount

Problem Description

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free. The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought. Given a 0-indexed integer array cost, where cost[i] denotes the cost of the i-th candy, return the minimum cost of buying all the candies.

Key Insights

• The strategy is to always buy the two most expensive candies available and take the least expensive candy for free.
• Sorting the array of candy costs allows us to efficiently select the candies to buy and the one to take for free.
• The algorithm can be implemented using a greedy approach, where we prioritize maximizing the discount received.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array of candy costs.
Space Complexity: O(1) - since we are using a constant amount of additional space.

Solution

To solve the problem, we can follow these steps:

1. Sort the array of candy costs in descending order.
2. Iterate through the sorted costs, purchasing the two most expensive candies at a time and skipping the third candy (which is taken for free).
3. Sum the costs of the purchased candies to get the total minimum cost.

This approach ensures that we maximize the discount by always considering the most expensive options first.

Code Solutions