Suggest an edit

Improve this article

Refine the answer for “How is the classic coin change problem solved using a greedy algorithm?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Greedy coin-change algorithm: at each step take the largest denomination that does not exceed the current remainder, subtract it, and repeat until the remainder reaches zero. It is optimal for "canonical" denomination sets (for example, 1, 5, 10, 25), but can give a suboptimal result for arbitrary sets. A fast implementation uses integer division and runs in O(k), where k is the number of denominations.

## Detailed answer

### The idea behind the greedy algorithm

We want to make change for amount S with the minimum number of coins from a set of denominations C. The greedy approach always picks the coin with the largest possible denomination that does not exceed the current remainder. This is a natural heuristic that turns out to be optimal not always, but often - for special ("canonical") denomination systems, which real-world currencies belong to.

### Step-by-step algorithm

1. Sort the denominations in descending order.
2. For each denomination c from the sorted list, take the maximum possible number of coins of that denomination: count = floor(S / c).
3. Reduce the remainder: S = S - count x c. Move to the next denomination.
4. Repeat until S becomes 0. If S > 0 after processing all denominations, change cannot be made with the given set.

### Example (canonical currency)

Denominations: {1, 5, 10, 25}. Amount: 63.

Greedy choice: 25 -> 25 -> 10 -> 1 -> 1 -> 1. 6 coins total. This is optimal.

```javascript
function greedyChange(coins, amount) {
  // Guard against garbage input
  if (!Array.isArray(coins) || coins.length === 0) throw new Error('coins must be a non-empty array');
  if (!Number.isInteger(amount) || amount < 0) throw new Error('amount must be a non-negative integer');

// Sort in descending order
  const sorted = [...coins].sort((a, b) => b - a);

const result = [];
  let remaining = amount;

for (const c of sorted) {
    if (c <= 0 || !Number.isInteger(c)) throw new Error('coin denominations must be positive integers');
    const count = Math.floor(remaining / c);
    if (count > 0) {
      result.push({ coin: c, count });
      remaining -= count * c;
    }
  }

if (remaining !== 0) {
    // Change is impossible (e.g., no 1-unit coin)
    return { ok: false, used: result, remaining };
  }

const totalCoins = result.reduce((s, x) => s + x.count, 0);
  return { ok: true, used: result, totalCoins };
}

// Example: canonical system {1,5,10,25}
console.log(greedyChange([1,5,10,25], 63));
// => { ok: true, used: [ {coin:25,count:2}, {coin:10,count:1}, {coin:1,count:3} ], totalCoins: 6 }
```

### Counterexample (where greedy is not optimal)

- Denominations {1, 3, 4}, amount 6: greedy gives 4 + 1 + 1 = 3 coins, optimal is 3 + 3 = 2 coins.
- Denominations {1, 5, 7}, amount 10: greedy gives 7 + 1 + 1 + 1 = 4 coins, optimal is 5 + 5 = 2 coins.

### Correctness and when greedy works

- Optimality on "canonical" denomination sets: real currencies (for example, {1, 5, 10, 25, 50}) are constructed so that the greedy algorithm is always optimal.
- Sufficient (but not necessary) conditions: `c1 = 1`, and each subsequent denomination is a multiple of the previous one (for example, {1, 2, 4, 8, ...}); or a "superincreasing" system, where each next denomination is strictly greater than the sum of all smaller ones. In such cases, an exchange argument proves the optimality of the greedy choice.
- For arbitrary sets there are no guarantees, and greedy can lose to dynamic programming.

### Complexity

If integer division is used (as in the code), we perform one action per denomination, i.e. O(k), where k is the number of denominations (plus O(k log k) for sorting, if the denominations are not pre-sorted). If coins are subtracted one at a time, the complexity is O(M), where M is the total number of coins issued.

### Implementation (JavaScript)

```javascript
// Greedy change: always pick the largest suitable coin
function greedyChange(coins, amount) {
  if (!Array.isArray(coins) || coins.length === 0) throw new Error('coins must be a non-empty array');
  if (!Number.isInteger(amount) || amount < 0) throw new Error('amount must be a non-negative integer');

const sorted = [...new Set(coins)].sort((a, b) => b - a); // deduplicate and sort
  if (sorted.some(c => !Number.isInteger(c) || c <= 0)) throw new Error('all coin denominations must be positive integers');

const used = [];
  let remaining = amount;

for (const c of sorted) {
    const cnt = Math.floor(remaining / c);
    if (cnt > 0) {
      used.push({ coin: c, count: cnt });
      remaining -= cnt * c;
    }
  }

return {
    ok: remaining === 0,
    used,
    remaining,
    totalCoins: used.reduce((s, x) => s + x.count, 0)
  };
}

// Examples
console.log('63 with {1,5,10,25}:', greedyChange([1,5,10,25], 63));
console.log('6 with {1,3,4}:', greedyChange([1,3,4], 6)); // greedy gives 3 coins, not optimal
console.log('10 with {1,5,7}:', greedyChange([1,5,7], 10)); // greedy gives 4 coins, not optimal
```

### When a dynamic approach is needed

If the denomination set is not canonical, or a guaranteed minimum number of coins is required for any input, use dynamic programming (for example, the classic algorithm with a dp table over the amount). It gives the optimum in O(k*S) time and O(S) memory.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts848 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.