Minimum Cost of Buying Candies With Discount — Solution
Minimum Cost of Buying Candies With Discount solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Cost of Buying Candies With Discount is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A shop runs an offer: for every two candies you buy, you may take a third candy for free, as long as the free candy costs no more than the cheaper of the two you paid for.
cost[i] is the price of candy i. Return the minimum total you must pay to take home all the candies.
Example 1
Input: cost = [7,3,5]
Output: 12
Explanation: Pay for 7 and 5, take 3 free.
Example 2
Input: cost = [4,4,4,4,4,4]
Output: 16
Explanation: Two rounds of 'pay for two, take one': four candies paid, two free.
Example 3
Input: cost = [9]
Output: 9
Constraints
1 <= cost.length <= 1001 <= cost[i] <= 100
Hints for Minimum Cost of Buying Candies With Discount
Hint 1
The free candy can never be pricier than the two you pay for — so the two most expensive candies can never be free.
Hint 2
Group candies from most to least expensive.
Hint 3
Sort in descending order and skip every third candy (indices 2, 5, 8, ...).
How to solve Minimum Cost of Buying Candies With Discount
Sort prices in descending order and take candies in groups of three: pay for the first two of each group and get the third free. Each group's free candy is as expensive as the rule allows.
Approach
- Sort
costin descending order. - Sum every price whose index
isatisfiesi % 3 != 2. - Return the sum.
Why it works
In any valid purchase, the k-th free candy must be preceded by at least 2k paid candies that are at least as expensive, so at most k of the top 3k candies can be free. The descending grouping frees exactly the 3k-th most expensive candy for every k, which is the best possible at every prefix — so it minimises what is paid.
Complexity
- Time —
O(n log n) - Space —
O(1) besides the sort
Pitfalls
- Sorting ascending and freeing every third from the cheap end gives away cheap candies and pays for expensive ones.
- A leftover group of one or two candies has no free item.
- The free candy must cost at most the cheaper paid one — equality is allowed.
Reference solution
Python
from typing import List
def minimumCost(cost: List[int]) -> int:
ordered = sorted(cost, reverse=True)
return sum(c for i, c in enumerate(ordered) if i % 3 != 2)Java
public static int minimumCost(int[] cost) {
int[] sorted = cost.clone();
Arrays.sort(sorted);
int total = 0, n = sorted.length;
for (int i = 0; i < n; i++) {
if (i % 3 != 2) total += sorted[n - 1 - i];
}
return total;
}C++
int minimumCost(vector<int>& cost) {
vector<int> sorted(cost);
sort(sorted.rbegin(), sorted.rend());
int total = 0;
for (int i = 0; i < (int)sorted.size(); i++) {
if (i % 3 != 2) total += sorted[i];
}
return total;
}JavaScript
var minimumCost = function(cost) {
var sorted = cost.slice().sort(function(a, b) { return b - a; });
var total = 0;
for (var i = 0; i < sorted.length; i++) {
if (i % 3 !== 2) total += sorted[i];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms