DSA Greedy Coin Change

How it works

For a coin system, repeatedly taking the largest fitting denomination works for some systems but not arbitrary ones. The fixture uses denominations one, three and four and asks for six. The greedy result uses three coins, while two threes achieve the same amount with two. This is not a claim that every coin problem should use the same dynamic program; first state whether supply is unlimited, denominations are positive integers and exact change is required.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as greedy-counterexample.py and run python greedy-counterexample.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def largest_first(coins, amount):
    if type(amount) is not int or amount < 0 or any(type(coin) is not int or coin < 1 for coin in coins):
        raise ValueError("Positive integer coins and nonnegative amount required")
    chosen = []
    for coin in sorted(coins, reverse=True):
        while coin <= amount:
            amount -= coin
            chosen.append(coin)
    return chosen, amount

chosen, remainder = largest_first([1, 3, 4], 6)
print(chosen, remainder)
print([3, 3], len([3, 3]) < len(chosen))

Expected result

[4, 1, 1] 0
[3, 3] True

Both choices make the amount exactly, but only the second has the smaller count. The helper assumes positive integer denominations and is shown solely on that fixed trusted input; validating arbitrary received denominations belongs at its boundary.

Time, space and assumptions

Sorting k denominations costs O(k log k), then this loop does work proportional to the number C of chosen coins. It stores O(C) output; that work is not an optimality proof.