About

The coin change problem is a classical optimization challenge in combinatorics and computer science. Given a target amount A and a set of coin denominations D = {d₁, d₂, …, d_n}, the goal is to find the minimum number of coins whose values sum exactly to A. A naive greedy approach (always pick the largest coin) fails for many denomination sets. For example, with coins {1, 3, 4} and target 6, greedy yields 4+1+1 (3 coins), while the optimal is 3+3 (2 coins). This tool uses bottom-up dynamic programming with traceback to guarantee the true minimum.

This calculator also reports the total number of distinct ways to make change and provides a full coin-by-coin breakdown. It supports preset denominations for 12 countries. Note: the tool assumes an unlimited supply of each denomination and integer-valued amounts. For fractional currencies, enter amounts in the smallest unit (e.g., cents, pence).

Formulas

The minimum coin count is computed via bottom-up dynamic programming. Define dp[i] as the minimum number of coins to make amount i.

dp[0] = 0

dp[i] = min(dp[i − d_j] + 1) for all d_j ≤ i

Time complexity: O(A ⋅ n), where A is the target amount and n is the number of denominations. Space complexity: O(A).

The total number of distinct combinations uses a separate DP. Define ways[i] as the count of combinations summing to i:

ways[0] = 1

For each coin d_j: ways[i] = ways[i] + ways[i − d_j] for i ≥ d_j

Where dp[i] = minimum coins for amount i, d_j = value of j-th denomination, A = target amount, n = number of distinct coin types, ways[i] = number of distinct combinations for amount i.

Reference Data

Country	Currency	Denominations (smallest unit)	Notes
United States	$ USD	1, 5, 10, 25, 50, 100	Penny, Nickel, Dime, Quarter, Half-Dollar, Dollar
European Union	€ EUR	1, 2, 5, 10, 20, 50, 100, 200	Cent to 2€
United Kingdom	£ GBP	1, 2, 5, 10, 20, 50, 100, 200	Penny to £2
Japan	¥ JPY	1, 5, 10, 50, 100, 500	No fractional currency
Canada	$ CAD	5, 10, 25, 100, 200	Penny eliminated in 2013
Australia	$ AUD	5, 10, 20, 50, 100, 200	1c and 2c removed 1992
India	₹ INR	1, 2, 5, 10, 20	Rupee coins (paise rarely used)
Switzerland	CHF	5, 10, 20, 50, 100, 200, 500	Rappen to 5 Fr
China	¥ CNY	1, 5, 10, 50, 100	Fen/Jiao/Yuan coins
Brazil	R$ BRL	5, 10, 25, 50, 100	Centavo to 1 Real
Mexico	$ MXN	10, 20, 50, 100, 200, 500, 1000	Centavo to 10 Pesos
Classic CS Example	Abstract	1, 3, 4	Demonstrates greedy failure at A = 6
Fibonacci Coins	Abstract	1, 2, 3, 5, 8, 13	Interesting non-standard system
Binary Powers	Abstract	1, 2, 4, 8, 16, 32, 64	Greedy always optimal (canonical)

Frequently Asked Questions

The greedy algorithm selects the largest denomination first and repeats. This works for canonical coin systems (like US coins) where the denomination ratios guarantee optimality. However, for non-canonical sets like {1, 3, 4}, greedy picks 4 + 1 + 1 = 3 coins for amount 6, while the optimal is 3 + 3 = 2 coins. Dynamic programming guarantees the global minimum by evaluating all sub-problems.

If no denomination of 1 exists in the set, certain amounts become unreachable. For example, denominations {3, 5} cannot produce amount 7. The calculator detects this when dp[A] remains at infinity and reports the amount as impossible.

The algorithm runs in O(A × n) time and O(A) space. For A up to 1,000,000 with 8 denominations, computation takes under 100ms in modern browsers. This calculator caps at 10,000,000 to prevent excessive memory allocation (approximately 40MB for the DP array).

Minimum coins answers: what is the fewest coins needed? Total combinations answers: how many different ways exist to make this amount? For US coins and 100 cents, the minimum is 4 quarters, but there are 242 distinct combinations including mixes of pennies, nickels, dimes, and quarters.

No. The DP algorithm iterates over all denominations for each sub-amount. The order of denominations in the input does not affect correctness. Internally, denominations are sorted in ascending order for the traceback reconstruction, which prefers larger coins first for cleaner output display.

Yes. A coin system is called canonical if greedy always produces the minimum. All standard national currencies are canonical by design. The calculator always runs full DP regardless, so results are correct for both canonical and non-canonical systems. The greedy comparison column helps you identify whether your custom denomination set is canonical.