✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-189

Minimum Coin Change — Greedy Approach

Understand how a greedy algorithm attempts to make a target amount using the largest available coin denominations first, and why this method does not always produce an optimal answer.

Explanation

Overview

The Greedy Coin Change Approach attempts to form a target amount using the fewest possible coins by repeatedly selecting the largest denomination that does not exceed the remaining amount. It is efficient for certain denomination systems, but it is not guaranteed to work optimally for every possible set of denominations.

Key concepts

Largest-denomination-first strategy; Local optimal choice; Greedy selection; Minimum coin count; Greedy-choice property; Counterexamples

Variables

amount: The target amount to be formed.; coins: The available coin denominations.; coin: The denomination selected at the current step.; remaining: The amount that still needs to be formed.; count: The total number of selected coins.

Complexity

sorting: O(C log C) time.; selection: O(K) time for K selected coins when each selection is processed individually.; overall: O(C log C + K) time for this implementation, where C is the number of denominations.; space: O(K) space when the selected coins are stored.

Example

coins: 1; 5; amount: 63; selectedCoins: 25; 25; minimumCoins: 6; explanation: The greedy method selects the largest possible denomination at each step. For this denomination system, it produces an optimal solution for the example.

Pseudocode

function greedyCoinChange(coins, amount):
sort coins in descending order
result = []
remaining = amount
for coin in coins:
while coin <= remaining:
result.append(coin)
remaining -= coin
if remaining != 0:
return failure
return result

Applications

Currency change-making.; Cash-handling systems.; Vending machines.; Greedy algorithm demonstrations.; Comparing greedy algorithms with dynamic programming.

Variables

Amount

The target amount to be formed.

Coins

The available coin denominations.

Coin

The denomination selected at the current step.

Remaining

The amount that still needs to be formed.

Count

The total number of selected coins.

Example or application

Coins

  • 1

  • 5

  • 10

  • 25

Amount

63

Selected Coins

  • 25

  • 25

  • 10

  • 1

  • 1

  • 1

Minimum Coins

6

Explanation

The greedy method selects the largest possible denomination at each step. For this denomination system, it produces an optimal solution for the example.

Definition

The Greedy Coin Change Approach attempts to form a target amount using the fewest possible coins by repeatedly selecting the largest denomination that does not exceed the remaining amount. It is efficient for certain denomination systems, but it is not guaranteed to work optimally for every possible set of denominations.

Mathematical Representation

remaining = amount; repeatedly choose the largest denomination coin c satisfying c <= remaining, then set remaining = remaining - c.

Counterexample

Coins

  • 1

  • 3

  • 4

Amount

6

Greedy Selection

  • 4

  • 1

  • 1

Greedy Coin Count

3

Optimal Selection

  • 3

  • 3

Optimal Coin Count

2

Explanation

The greedy algorithm chooses a coin of value 4 first, leaving 2, which requires two more coins. Choosing two coins of value 3 gives the target using only two coins.

Greedy Strategy

  • Sort denominations in descending order.

  • Start with the full target amount.

  • Choose the largest denomination that does not exceed the remaining amount.

  • Subtract that denomination from the remaining amount.

  • Repeat until the amount becomes zero or no valid denomination remains.

  • If a positive remainder cannot be formed, report that the greedy attempt failed.

Pseudocode

function greedyCoinChange(coins, amount):
sort coins in descending order
result = []
remaining = amount
for coin in coins:
while coin <= remaining:
result.append(coin)
remaining -= coin
if remaining != 0:
return failure
return result

Complexity

Sorting

O(C log C) time.

Selection

O(K) time for K selected coins when each selection is processed individually.

Overall

O(C log C + K) time for this implementation, where C is the number of denominations.

Space

O(K) space when the selected coins are stored.

Key Concepts

  • Largest-denomination-first strategy

  • Local optimal choice

  • Greedy selection

  • Minimum coin count

  • Greedy-choice property

  • Counterexamples

Advantages

  • Simple to understand and implement.

  • Can be very efficient for suitable currency systems.

  • Often produces optimal results for canonical coin systems.

  • Requires little additional memory when only the count is tracked.

Limitations

  • Does not guarantee a minimum number of coins for arbitrary denominations.

  • May fail to form the target amount even when a valid combination exists.

  • The optimality of a denomination system must be established rather than assumed.

  • Dynamic programming is more reliable when arbitrary denominations are used.

Applications

  • Currency change-making.

  • Cash-handling systems.

  • Vending machines.

  • Greedy algorithm demonstrations.

  • Comparing greedy algorithms with dynamic programming.

Related Topics

  • Coin Change Problem

  • Dynamic Programming

  • Greedy Algorithms

  • Unbounded Knapsack Problem

Practice Question

Using denominations [1, 3, 4], what does the greedy approach select for amount 6, and is it optimal?

Practice Answer

It selects [4, 1, 1], using 3 coins. It is not optimal because [3, 3] uses only 2 coins.

Learning Objectives

  • Explain the central idea and purpose of minimum coin change — greedy approach.

  • Identify the assumptions, inputs, and conditions relevant to minimum coin change — greedy approach.

  • Evaluate an application of minimum coin change — greedy approach for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Greedy Algorithms and Optimization

Suggest a correction or source · More in Algorithms & Data Structures