Minimum Cost of Buying Candies With Discount
On this page 
Problem Statement
Imagine you're shopping for candies at a store that has a special offer: for every two candies you buy, you can choose a third candy to get for free. However, the free candy must be priced at or below the cost of the less expensive of the two candies you purchased.
Given an array called cost, where each element represents the price of a candy, your task is to calculate the minimum total cost needed to buy all the candies, taking advantage of this offer.
Example 1
Input: cost = [1,2,3]
Output: 5
Example 2
Input: cost = [6,5,7,9,2,2]
Output: 23
Constraints
1 <= cost.length <= 100: The number of candies will be between 1 and 100.1 <= cost[i] <= 100: Each candy’s cost will be between 1 and 100.
Approach:
Understanding the Discount: For every two candies purchased, you can select a third candy to be free, provided its cost does not exceed the minimum of the two candies you bought.
Optimal Strategy: To minimize your total expenditure:
Sort the candies in descending order based on their prices.
Purchase the most expensive candies first to make the most out of the free candy offer.
Implementation Steps:
Sort the candy costs in descending order.
Iterate through the sorted list, buying candies in pairs and applying the discount optimally to minimize the total cost.
Solution 1: Greedy Approach
function minCostGreedy(cost) {
cost.sort((a, b) => b - a);
let totalCost = 0;
for (let i = 0; i < cost.length; i++) {
if ((i % 3) !== 2) {
totalCost += cost[i];
}
}
return totalCost;
}
const cost1 = [1,2,3];
minCostGreedy(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostGreedy(cost2); //output: 23
Solution 2: Sorting and Grouping Approach
function minCostSortingAndGrouping(cost) {
cost.sort((a, b) => b - a);
let totalCost = 0;
for (let i = 0; i < cost.length; i += 3) {
totalCost += cost[i] + (cost[i + 1] || 0);
}
return totalCost;
}
const cost1 = [1,2,3];
minCostSortingAndGrouping(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostSortingAndGrouping(cost2); //output: 23
Solution 3: Iterative Pairing Approach
function minCostIterativePairing(cost) {
cost.sort((a, b) => b - a);
let totalCost = 0;
for (let i = 0; i < cost.length; i += 3) {
totalCost += cost[i] + (cost[i + 1] || 0);
}
return totalCost;
}
const cost1 = [1,2,3];
minCostIterativePairing(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostIterativePairing(cost2); //output: 23
Solution 4: Recursive Approach
function minCostRecursive(cost) {
function helper(arr) {
if (arr.length <= 2) return arr.reduce((sum, val) => sum + val, 0);
arr.sort((a, b) => b - a);
return arr[0] + arr[1] + helper(arr.slice(3));
}
return helper(cost);
}
const cost1 = [1,2,3];
minCostRecursive(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostRecursive(cost2); //output: 23
Solution 5: Dynamic Programming Approach
function minCostDynamicProgramming(cost) {
const n = cost.length;
if (n <= 2) return cost.reduce((sum, val) => sum + val, 0);
cost.sort((a, b) => b - a);
let totalCost = 0;
for (let i = 0; i < n; i += 3) {
totalCost += cost[i] + (cost[i + 1] || 0);
}
return totalCost;
}
const cost1 = [1,2,3];
minCostDynamicProgramming(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostDynamicProgramming(cost2); //output: 23
Solution 6: Greedy with Sorting and Pairing Approach
function minCostGreedySortingPairing(cost) {
cost.sort((a, b) => b - a);
let totalCost = 0;
for (let i = 0; i < cost.length; i += 3) {
totalCost += cost[i] + (cost[i + 1] || 0);
}
return totalCost;
}
const cost1 = [1,2,3];
minCostGreedySortingPairing(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostGreedySortingPairing(cost2); //output: 23
Solution 7: Pair-by-Pair Approach
function minCostPairByPair(cost) {
cost.sort((a, b) => b - a);
let totalCost = 0;
for (let i = 0; i < cost.length; i += 3) {
totalCost += cost[i] + (cost[i + 1] || 0);
}
return totalCost;
}
const cost1 = [1,2,3];
minCostPairByPair(cost1); //output: 5
const cost2 = [6,5,7,9,2,2];
minCostPairByPair(cost2); //output: 23