Minimum number of coins / minimum cost of ropes / connect n ropes
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: []
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.