Minimum Cost of Buying Candies With Discount

Minimum Cost of Buying Candies With Discount - 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, 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-th candy, return the minimum cost of buying all the candies.

Input & Output

Example 1 — Basic Case

$ Input: cost = [1,2,3,4,5,6]

› Output: 16

💡 Note: Sort to [6,5,4,3,2,1]. Group 1: pay 6+5=11, get 4 free. Group 2: pay 3+2=5, get 1 free. Total = 11+5 = 16.

Example 2 — Minimum Size

$ Input: cost = [6,5,7,9,2,2]

› Output: 23

💡 Note: Sort to [9,7,6,5,2,2]. Group 1: pay 9+7=16, get 6 free. Group 2: pay 5+2=7, get 2 free. Total = 16+7 = 23.

Example 3 — Edge Case

$ Input: cost = [5,5]

› Output: 10

💡 Note: Only 2 candies, no free candy available. Must buy both: 5+5 = 10.

Constraints

1 ≤ cost.length ≤ 100
1 ≤ cost[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array of candy costs [1,2,3,4,5,6]

Process

Sort descending and group by 3, pay for 2 most expensive per group

Output

Minimum total cost to buy all candies

Key Takeaway

🎯 Key Insight: Sort candies by price descending, then greedily group consecutive triplets to maximize savings

Asked in

a Amazon 15 M Microsoft 8

The key insight is to sort candies by price in descending order, then group them in sets of 3 where we pay for the 2 most expensive and get the cheapest free. This greedy approach ensures maximum savings. Best approach is Greedy Sorting with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Groupings	O(n!)	O(n)	Try all possible ways to group candies into sets of 3 and find minimum cost
Greedy - Sort and Group Optimally	O(n log n)	O(1)	Sort prices in descending order, then take every 3rd item for free

Brute Force - Try All Groupings — Algorithm Steps

Generate all possible ways to group candies into sets of 3
For each grouping, calculate cost (pay for 2 most expensive, get cheapest free)
Return minimum cost among all groupings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Groups

Create all possible groups of 3 candies

Calculate Cost

For each group, pay for 2 most expensive

Find Minimum

Return the grouping with minimum total cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int backtrack(int index, int currentCost, int* used, int* cost, int n) {
    if (index == n) {
        return currentCost;
    }
    
    if (used[index]) {
        return backtrack(index + 1, currentCost, used, cost, n);
    }
    
    int minCost = INT_MAX;
    
    for (int i = index + 1; i < n; i++) {
        if (used[i]) continue;
        for (int j = i + 1; j < n; j++) {
            if (used[j]) continue;
            
            int group[3] = {cost[index], cost[i], cost[j]};
            qsort(group, 3, sizeof(int), compare);
            int groupCost = group[1] + group[2];
            
            used[index] = used[i] = used[j] = 1;
            int totalCost = backtrack(index + 1, currentCost + groupCost, used, cost, n);
            if (totalCost < minCost) {
                minCost = totalCost;
            }
            used[index] = used[i] = used[j] = 0;
        }
    }
    
    return minCost;
}

int solution(int* cost, int n) {
    if (n <= 2) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += cost[i];
        }
        return sum;
    }
    
    int* used = (int*)calloc(n, sizeof(int));
    int result = backtrack(0, 0, used, cost, n);
    free(used);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int cost[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        cost[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(cost, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!)

Generating all possible groupings requires factorial time

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for current grouping and recursion stack

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~12 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Groupings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler