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

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

✓ Brute Force - Try All Groupings

⏱️ Time: O(n!) Space: O(n)

Generate all possible combinations of grouping candies into sets of 3, where each group pays for 2 and gets 1 free (the cheapest in the group). Calculate total cost for each grouping and return minimum.

Greedy - Sort and Group Optimally

⏱️ Time: O(n log n) Space: O(1)

Sort all candy prices in descending order. Group them in sets of 3 consecutively, where we pay for the 2 most expensive and get the cheapest free. This greedy approach ensures we always get maximum savings.

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* remaining, int remainingSize, int currentCost) {
    if (remainingSize == 0) {
        return currentCost;
    }
    
    if (remainingSize <= 2) {
        int sum = 0;
        for (int i = 0; i < remainingSize; i++) {
            sum += remaining[i];
        }
        return currentCost + sum;
    }
    
    int minCost = INT_MAX;
    
    for (int i = 0; i < remainingSize; i++) {
        for (int j = i + 1; j < remainingSize; j++) {
            for (int k = j + 1; k < remainingSize; k++) {
                int group[3] = {remaining[i], remaining[j], remaining[k]};
                qsort(group, 3, sizeof(int), compare);
                int groupCost = group[1] + group[2];
                
                int* newRemaining = (int*)malloc((remainingSize-3) * sizeof(int));
                int newSize = 0;
                for (int x = 0; x < remainingSize; x++) {
                    if (x != i && x != j && x != k) {
                        newRemaining[newSize++] = remaining[x];
                    }
                }
                
                int totalCost = backtrack(newRemaining, newSize, currentCost + groupCost);
                if (totalCost < minCost) {
                    minCost = totalCost;
                }
                free(newRemaining);
            }
        }
    }
    
    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;
    }
    
    return backtrack(cost, n, 0);
}

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

⚡ Linearithmic

Space Complexity

O(n)

Storage for current grouping and recursion stack

✓ Linear 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

Minimum Cost of Buying Candies With Discount - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Groupings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler