Minimum coin change
Given coin denominations and a target amount, find the minimum number of coins needed, or -1 if the amount cannot be formed.
Course progress
Problem 35 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
coins = [1, 2, 5]; amount = 11
Expected output
3
What is happening?
The best composition is 5 + 5 + 1. It reaches 11 with three coins, and no two available coins can total 11.
Solution strategy
Build the right mental model
Build answers from 0 upward. For every reachable amount, try adding each coin and keep the smallest count found for the new amount.
Core concepts
dynamic programming · arrays
Complexity
Time O(amount × coins), space O(amount).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for coin-change
using System;
class Program
{
static int MinimumCoins(int[] coins, int amount)
{
int[] best = new int[amount + 1];
for (int i = 0; i < best.Length; i++) best[i] = amount + 1;
best[0] = 0;
for (int value = 1; value <= amount; value++)
foreach (int coin in coins)
if (coin <= value) best[value] = Math.Min(best[value], best[value - coin] + 1);
return best[amount] > amount ? -1 : best[amount];
}
static void Main()
{
Console.WriteLine(MinimumCoins(new[] { 1, 2, 5 }, 11));
}
}Knowledge check
Questions students often ask
What is the main idea behind minimum coin change?
Build answers from 0 upward. For every reachable amount, try adding each coin and keep the smallest count found for the new amount.
What is the time and space complexity of this solution?
Time O(amount × coins), space O(amount).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.