Formatted question description: https://leetcode.ca/all/2144.html

# 2144. Minimum Cost of Buying Candies With Discount (Easy)

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 ^{th}*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 theonlyway 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 <= 100`

`1 <= cost[i] <= 100`

**Similar Questions**:

## Solution 1. Greedy

Sort the costs in descending order.

From left to right, after taking every two candies, skip one candy.

```
// OJ: https://leetcode.com/problems/minimum-cost-of-buying-candies-with-discount/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int minimumCost(vector<int>& A) {
sort(begin(A), end(A), greater<>());
int ans = 0, N = A.size();
for (int i = 0; i < N; ++i) {
ans += A[i++];
if (i < N) ans += A[i++];
}
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/minimum-cost-of-buying-candies-with-discount/discuss/1709728/C%2B%2B-Greedy-%2B-Sorting