LeetCode 2144. Minimum Cost of Buying Candies With Discount
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?ith?candy, return?the?minimum cost?of buying?all?the candies.
?
Example 1:
Input: cost = [1,2,3]Output: 5Explanation: 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: 23Explanation: 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: 10Explanation: 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 <= 1001 <= cost[i] <= 100
Accepted
33,141
Submissions
54,362
Seen this question in a real interview before?
Yes
No
Companies
Related Topics
Similar Questions
Hide 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?
Hide Hint 2
How can we generalize this approach to maximize the costs of the candies we get for free?
Hide Hint 3
Can “sorting” the array help us find the minimum cost?
Hide Hint 4
If we consider costs from high to low, what is the maximum cost of a single candy that we can get for free?
Hide Hint 5
How can we generalize this approach to maximize the costs of the candies we get for free?
Hide Hint 6
Can “sorting” the array help us find the minimum cost?
對(duì)于最大的值，肯定只能自費(fèi)了，次之也是只能自費(fèi)的，第3個(gè)才能免費(fèi)的，
所以需要先排序，然后判斷跟3余數(shù)的關(guān)系去累加，也可以依次遍歷（從后向前到3了，免費(fèi)1次）。
Runtime:?2 ms, faster than?100.00%?of?Java?online submissions for?Minimum Cost of Buying Candies With Discount.
Memory Usage:?42 MB, less than?48.10%?of?Java?online submissions for?Minimum Cost of Buying Candies With Discount.
