Number of Coins

Time

O (M \cdot V)

Space

O (M \cdot V)

Problem

GeeksforGeeksOpen original problem

Given a value V and array coins[] of size M, the task is to make the change for V cents, given that you have an infinite supply of each of coins - coins₁, coins₂, ..., coins_m valued coins. Find the minimum number of coins to make the change. If not possible to make change then return -1.

Solution approach

Intuition

This is an unbounded knapsack: every coin can be used any number of times, and we want the fewest coins whose values add up to V. Let dp[i][j] be the minimum number of coins, using only the first i coin types, that sum to exactly j. Trying every combination of coins directly is exponential, but each state depends only on two smaller states.

For the i-th coin there are two choices:

Take it (it stays available, since coins are unlimited): $dp[i][j] = \min(dp[i][j],\ dp[i][j - coins[i-1]] + 1)$
Skip it: $dp[i][j] = \min(dp[i][j],\ dp[i-1][j])$

Algorithm

Sort coins (not needed for correctness) and create a (M + 1) x (V + 1) table dp filled with INT_MAX, meaning “not reachable”. It uses long long so that INT_MAX + 1 does not overflow.
For each coin index i from 1 to M, set dp[i][0] = 0, since zero coins make sum 0.
For each sum j from 1 to V, apply the “take” transition when coins[i - 1] <= j, then the “skip” transition.
If dp[M][V] is still at least INT_MAX, the sum cannot be formed, so return -1; otherwise return dp[M][V].

Complexity

Time: $O(M \cdot V)$ — every cell of the dp table is filled once in $O(1)$ ; sorting adds only $O(M \log M)$ .
Space: $O(M \cdot V)$ — the full 2D dp table.

Edge cases

Unreachable value, e.g. coins = [2], V = 3: the cell stays at INT_MAX and the function returns -1.

Code

1
class Solution {
2
   public:
3
    int minCoins(int coins[], int M, int V) {
4
        sort(coins, coins + M);
5
        vector<vector<long long>> dp(M + 1, vector<long long>(V + 1, INT_MAX));
6
        for (int i = 1; i <= M; i++) {
7
            dp[i][0] = 0;
8
            for (int j = 1; j <= V; j++) {
9
                if (coins[i - 1] <= j) {
10
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
11
                }
12
                dp[i][j] = min(dp[i][j], dp[i - 1][j]);
13
            }
14
        }
15
        if (dp[M][V] >= INT_MAX) return -1;
16
        return (int)dp[M][V];
17
    }
18
};

Give it a try first

Attempt the problem on GeeksforGeeks — the code will still be here.