#2144
Minimum Cost of Buying Candies With Discount
pupil · 355 · lc easy +23 · verified · 62.7% accepted · 690 likes · top 64%
Description
A shop offers a buy-two-get-one-free deal on candies. For every two candies purchased, you receive one candy for free, provided its cost does not exceed the lesser of the two purchased prices.
- For example, with candies costing 1, 2, 3, 4, buying the 2- and 3-cost candies lets you take the 1-cost candy for free, but not the 4-cost candy.
Given a 0-indexed integer array cost where cost[i] is the price of the ith candy, return the minimum total cost to purchase 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.
Code
1
2
3