Minimum number of coins / minimum cost of ropes / connect n ropes

Easy

Problem

(1) Minimum coins: using Indian currency denominations (1, 2, 5, 10, 20, 50, 100, 500, 2000), make change for V with the fewest notes and coins — greedy works for this canonical system. (2) Connect ropes: joining two ropes costs the sum of their lengths; minimise the total cost of joining them all.

Example 1

Input:  V = 70
Output: [50, 20]

Example 2

Input:  ropes [4, 3, 2, 6]
Output: 29

Also asked as: Greedy Algorithm to find Minimum number of Coins · Minimum Cost of ropes

Test cases

Case 1

Input:    70
Expected: [50,20]

Case 2

Input:    43
Expected: [20,20,2,1]

Case 3

Input:    121
Expected: [100,20,1]

Case 4

Input:    0
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Coins: take the largest denomination that fits, repeatedly

Time O(amount / minCoin) or O(coins·log)Space O(1)

For canonical coin systems (1, 2, 5, 10, …), greedily using the biggest coin ≤ the remaining amount is optimal. (For arbitrary systems use DP — see "Coin Change".)

function minCoins(amount, coins = [1, 2, 5, 10, 20, 50, 100, 500, 2000]) {
coins.sort((a, b) => b - a);
const used = [];
for (const c of coins) while (amount >= c) { amount -= c; used.push(c); }
return used;
}

Connect n ropes with minimum cost: min-heap, always join the two shortest ropes and add the combined length to the cost (Huffman-style) — see the Heap section.