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.
Input: cost = [1,2,3]
Output: 5
Input: cost = [6,5,7,9,2,2]
Output: 23
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.
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
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
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
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
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
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
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