Log inSign up
easyGeeksforGeeksNot Started

Minimum Number of Coins

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a value V, find the minimum number of coins and/or notes needed to make the change for V using Indian currency denominations: [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000].

Assume that you have an infinite supply of each denomination. Return the list of coins/notes used to form V in descending order.

Example 1 · Example 1: Value 43:

Input: V = 43
Output: [20, 20, 2, 1]
Explanation: Take 20 (V=23) -> Take 20 (V=3) -> Take 2 (V=1) -> Take 1 (V=0). Total = 4 coins.

Example 2 · Example 2: Value 1000:

Input: V = 1000
Output: [500, 500]
Explanation: Take 500 (V=500) -> Take 500 (V=0). Total = 2 coins.

Constraints:

  • 1 <= V <= 106
  • Denominations: [1, 2, 5, 10, 20, 50, 100, 200, 500, 2000]

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish canonical currency systems (where greedy works) from arbitrary systems (where DP is mandatory).
  • Explain the greedy choice property in currency change.
  • Implement the greedy change maker across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Standard real-world currency change problems.
  • Infinite supply of coins.
  • Minimize total coin count.

Algorithmic Decision Tree:

  • If canonical currency -> Greedy largest denomination first (O(N) time).
  • If arbitrary denominations -> Dynamic Programming (Unbounded Knapsack).

Connected Patterns:

Lemonade ChangeCoin Change (LeetCode 322)Integer to Roman

1. Recursive Minimum Coin Search

Intuition

Recursively branch on including each possible denomination to find the minimal coin combination.

Algorithm

  1. Step 1: Define solve(rem) returning min coins needed.
  2. Step 2: If rem == 0, return 0. If rem < 0, return infinity.
  3. Step 3: Loop through all denominations d: ans = min(ans, 1 + solve(rem - d)).
  4. Step 4: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int coins[10] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000};
9 int solve(int rem) {
10 if (rem == 0) return 0;
11 if (rem < 0) return 1e9;
12 int ans = 1e9;
13 for (int i = 9; i >= 0; --i) {
14 if (rem >= coins[i]) {
15 ans = min(ans, 1 + solve(rem - coins[i]));
16 break; // Canonical property allows early break
17 }
18 }
19 return ans;
20 }
21public:
22 vector<int> minPartition(int N) {
23 vector<int> res;
24 for (int i = 9; i >= 0; --i) {
25 while (N >= coins[i]) {
26 N -= coins[i];
27 res.push_back(coins[i]);
28 }
29 }
30 return res;
31 }
32};
33
34int main() {
35 Solution sol;
36 int V = 43;
37 vector<int> ans = sol.minPartition(V);
38 cout << "Coins for " << V << ": ";
39 for (int c : ans) cout << c << " ";
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(2^V)
  • Space complexity: O(V)

2. Unbounded Knapsack DP

Intuition

Maintain a dynamic programming table dp[i] where dp[i] is the minimum coins needed for amount i. Reconstruct the coins used.

Algorithm

  1. Step 1: Initialize dp array of size V + 1 with infinity; set dp[0] = 0.
  2. Step 2: Maintain a parent array lastCoin[V + 1] to trace back the chosen coins.
  3. Step 3: For i from 1 to V, and for each coin d in denominations:
  4. Step 4: If i >= d and dp[i - d] + 1 < dp[i]: dp[i] = dp[i - d] + 1, lastCoin[i] = d.
  5. Step 5: Trace back from V using lastCoin to recover all coins.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> minPartition(int N) {
10 vector<int> coins = {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000};
11 vector<int> dp(N + 1, 1e9);
12 vector<int> parent(N + 1, -1);
13 dp[0] = 0;
14
15 for (int i = 1; i <= N; ++i) {
16 for (int c : coins) {
17 if (i >= c && dp[i - c] + 1 < dp[i]) {
18 dp[i] = dp[i - c] + 1;
19 parent[i] = c;
20 }
21 }
22 }
23
24 vector<int> ans;
25 int curr = N;
26 while (curr > 0 && parent[curr] != -1) {
27 ans.push_back(parent[curr]);
28 curr -= parent[curr];
29 }
30 return ans;
31 }
32};
33
34int main() {
35 Solution sol;
36 int V = 43;
37 vector<int> ans = sol.minPartition(V);
38 cout << "Coins (DP): ";
39 for (int c : ans) cout << c << " ";
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(V * D)
  • Space complexity: O(V)

3. Greedy Largest Denomination First

Intuition

Iterate from the largest denomination downwards. Greedily take as many coins of the current denomination as possible using division and modulo.

Algorithm

  1. Step 1: Define constant array denominations: [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1].
  2. Step 2: Initialize result list ans.
  3. Step 3: Loop through each coin in descending order:
  4. Step 4: If N >= coin, compute count = N / coin. Append coin count times to ans, and set N = N % coin.
  5. Step 5: When N == 0, break early.
  6. Step 6: Return ans.

Interactive Trace for Minimum Number of Coins

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Check coin 20
Visual state
Values and pointers at this exact step
pointers
S
skipped
picked
pending
0
1
↑ current
2
Check / comparison
43 >= 20 (fits)
Decision / next transition
Add 20. V becomes 23.
Why this step matters

Step 1: Check coin 20. V = 43 >= 20. Pick 20. Remaining V = 23.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<int> minPartition(int N) {
9 int coins[] = {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
10 vector<int> ans;
11
12 for (int c : coins) {
13 if (N >= c) {
14 int count = N / c;
15 ans.insert(ans.end(), count, c);
16 N %= c;
17 }
18 if (N == 0) break;
19 }
20
21 return ans;
22 }
23};
24
25int main() {
26 Solution sol;
27 int V = 43;
28 vector<int> ans = sol.minPartition(V);
29 cout << "Coins for " << V << ": ";
30 for (int c : ans) cout << c << " ";
31 cout << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(D) where D is number of denominations
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive BranchingO(2^V)O(V) recursion stackRecursively try every denomination that fits the remaining value and return the branch yielding minimum coins.Exponential overlapping recursive tree.
2.Better — Unbounded Knapsack DPO(V * D) where D is number of denominationsO(V)Maintain dp[i] as the minimum coins to make value i. Fill dp table from 1 to V. Trace back to collect coins.Linear table filling up to V.
3.Optimal — Greedy Largest Denomination FirstOptimalO(D) where D is constant 10O(1) auxiliaryIterate denominations from 2000 down to 1. Greedily take as many of each coin as possible: add to answer and reduce remaining value.Loop over fixed denominations.
Back to DSA Sheet