2144. Minimum Cost of Buying Candies With Discount

2144. Minimum Cost of Buying Candies With Discount

Difficulty: Easy

Topics: Mid Level, Array, Greedy, Sorting, Biweekly Contest 70

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.

• For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the iᵗʰ candy, return the minimum cost of buying all the candies.

Example 1:

• Input: cost = [1,2,3]
• Output: 5
• Explanation:
  • We buy the candies with costs 2 and 3, and take the candy with cost 1 for free.
  • The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies.
  • Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free.
  • The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

• Input: cost = [6,5,7,9,2,2]
• Output: 23
• Explanation:
  • The way in which we can get the minimum cost is described below:
  • Buy candies with costs 9 and 7
  • Take the candy with cost 6 for free
  • We buy candies with costs 5 and 2
  • Take the last remaining candy with cost 2 for free
  • Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

• Input: cost = [5,5]
• Output: 10
• Explanation:
  • Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free.
  • Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Constraints:

• 1 <= cost.length <= 100
• 1 <= cost[i] <= 100

Hint:

1. If we consider costs from high to low, what is the maximum cost of a single candy that we can get for free?
2. How can we generalize this approach to maximize the costs of the candies we get for free?
3. Can “sorting” the array help us find the minimum cost?

Solution:

The solution reduces total cost by sorting candy prices in descending order and taking every third candy for free, because the discount allows a free candy whose price is ≤ the cheaper of the two purchased candies. Sorting descending and skipping every third item maximizes the value of free candies.

Approach:

• Sort the array in descending order so the most expensive candies are considered first.
• Iterate through the sorted list, adding the cost of each candy to the total except for every third candy.
• The index pattern (0, 1, 3, 4, 6, 7, …) ensures that after buying two candies, the next one is free.
• Sum all purchased candies and return the total.

Let's implement this solution in PHP: 2144. Minimum Cost of Buying Candies With Discount

<?php
/**
 * @param Integer[] $cost
 * @return Integer
 */
function minimumCost(array $cost): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minimumCost([1,2,3]) . "\n";               // Output: 5
echo minimumCost([6,5,7,9,2,2]) . "\n";         // Output: 23
echo minimumCost([5,5]) . "\n";                 // Output: 10
?>

Explanation:

• Sorting descending ensures that when we take a free candy, it’s the smallest possible among the remaining items.
• Index check (i % 3 != 2) means we skip adding the price for the third candy in every group of three.
• Example: costs sorted → 9, 7, 6, 5, 2, 2
  • Buy 9 (index 0), buy 7 (index 1), skip 6 (index 2), buy 5 (index 3), buy 2 (index 4), skip 2 (index 5)
  • Total = 9 + 7 + 5 + 2 = 23
• This greedy method works because taking a free candy from the smallest available prices is always optimal.

Complexity

• Time Complexity: O(n log n) — due to sorting.
• Space Complexity: O(1) — ignoring the input storage, only a few variables are used.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub