Problem

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 theminimum cost of buying all the candies.

Examples

Example 1

1
2
3

Input: cost = [1,2,3]
Output: 5
Explanation: Buy candies with costs 2 and 3, take the candy with cost 1 for free. Total cost = 2 + 3 = 5.

Example 2

1
2
3

Input: cost = [6,5,7,9,2,2]
Output: 23
Explanation: Buy candies with costs 9, 7, 6, 5, and take candies with costs 2, 2 for free. Total cost = 9 + 7 + 6 + 5 = 27, but you get two candies for free, so total cost = 23.

Example 3

1
2
3
4

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

Solution

Method 1 – Greedy Sorting

Intuition

To minimize the total cost, always buy the most expensive candies first. For every two candies bought, take the cheapest available (among the remaining) for free. Sorting the array in descending order allows us to always pick the most expensive ones to pay for, and skip every third candy (the free one).

Approach

  1. Sort the cost array in descending order.
  2. Iterate through the sorted array:
    • For every group of three candies, pay for the first two and skip the third (free).
    • Sum the cost of the candies you pay for.
  3. Return the total sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        sort(cost.rbegin(), cost.rend());
        int ans = 0;
        for (int i = 0; i < cost.size(); ++i) {
            if (i % 3 != 2) ans += cost[i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minimumCost(cost []int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(cost)))
    ans := 0
    for i, v := range cost {
        if i%3 != 2 {
            ans += v
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        int ans = 0, n = cost.length;
        for (int i = n - 1, cnt = 0; i >= 0; i--, cnt++) {
            if (cnt % 3 != 2) ans += cost[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun minimumCost(cost: IntArray): Int {
        cost.sortDescending()
        var ans = 0
        for (i in cost.indices) {
            if (i % 3 != 2) ans += cost[i]
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minimumCost(self, cost: list[int]) -> int:
        cost.sort(reverse=True)
        ans = 0
        for i, v in enumerate(cost):
            if i % 3 != 2:
                ans += v
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn minimum_cost(cost: Vec<i32>) -> i32 {
        let mut cost = cost;
        cost.sort_by(|a, b| b.cmp(a));
        let mut ans = 0;
        for (i, v) in cost.iter().enumerate() {
            if i % 3 != 2 {
                ans += v;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minimumCost(cost: number[]): number {
        cost.sort((a, b) => b - a);
        let ans = 0;
        for (let i = 0; i < cost.length; ++i) {
            if (i % 3 !== 2) ans += cost[i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) for sorting the array, where n is the number of candies.
  • 🧺 Space complexity: O(1) if sorting in-place, otherwise O(n) for a copy.