Minimum Cost of Buying Candies With Discount

Easy
1120.

Minimum Cost of Buying Candies With Discount

Minimum Cost of Buying Candies With Discount is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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 <= 100
  • 1 <= cost[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} cost
 * @return {number}
 */
var minimumCost = function(cost) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= cost[i] <= 100

Hints for Minimum Cost of Buying Candies With Discount

  1. 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.

  2. Hint 2

    Group candies from most to least expensive.

  3. 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

  1. Sort cost in descending order.
  2. Sum every price whose index i satisfies i % 3 != 2.
  3. 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