Home » Interview coding problems/challenges

Find minimum number of coins that make a given value

Minimum Coin Change: Here, we are going to learn how to find minimum number of coins that make a given value? This is a very popular coding problem which has been featured in interview rounds of many big companies such as Amazon, Morgan, Stanley, Oracle, Paytm, Samsung, Snapdeal and others. By Divyansh Jaipuriyar Last updated : April 21, 2024

Problem statement

Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change?

Input

The test case consists of V and N, V is the value of cents and N is the number of coins. The second line of each test case contains N input C[i], the value of available coins.

Output

Print the minimum number of coins to make the change, if not possible print "-1".

Example with Explanation

Input: 
N=5, V = 25
coins[] = {4,5,2,1,9}.

Output: 
Minimum 4 coins required
We can use one coin of 5 cents, 
two coins of 9 cents and one of 2 cents
(9+9+2+5)

Input: 
N=6, V = 256324
coins[] = {1,2,5,10,20,50}. 

Output: 
Minimum 5129 coins required

Find minimum number of coins that make a given value using recursive solution

We will start the solution with initially sum = V cents and at each iteration find the minimum coins required by dividing the problem into subproblems where we take {C1, C2, ..., CN} coin and decrease the sum V.

By C[i] (based on the coin we took). Whenever V becomes 0, this means we have a possible or otherwise there is no solution and we return -1;

Solution

To find the optimal answer, we return the minimum of all answers for which N became 0.

If V == 0, then 0 coins required.

We calculate the total required number of coins using the following function:

int mincoins(coins array[], size of the array, required sum);

So, initially the function call would be:

int mincoins(C,N,V);

Where C is the coins array, N is the size of the coin array and V is the required sum.

Now our idea is the get the minimum number of coins from the given array
and if the sum that we want to get if not possible from the given set of coins we will return -1.

So, let's see the function definition:

Function

Mincoins(int coins[],int N,int V):
	if V==0,then 0 coins are required
	if V>0:
	    mincoins{V,coins[0...N-1]}=min{1+mincoins{N-coins[i],coins[0...N-1]}}
        Where, i varies from 0 to N-1 and coins<=N
End Function

Pseudo Code

int Mincoins(coins[],N,V):
if(V==0)
	return 0 //base case
else{
	res=INT_MAX //if res=INT_MAX==-1 in the answer
	for(i=0;i<N;i++){
		sub;
		if(coins[i]>=V){ 
			// recursive call
            sub=1+mincoins(coins,N,V-coins[i]) 
			// assigning the min value to res
            res=min(res,subres) 
		}
	}
	return res//return the result of mincoins.
}

The recursive definition consists of the part:

mincoins{V,coins[0...N-1]}=min{1+mincoins{N-coins[i],coins[0...N-1]}}

This recursive part will generate a recursion tree where we can find many overlapping subproblems, hence we would solve by dynamic programming.

C++ implementation to find minimum number of coins that make a given value using recursive solution

#include <bits/stdc++.h>
using namespace std;

int mincoins(int C[], int N, int V)
{
    if (V == 0)
        return 0;
    int res = INT_MAX;
    for (int i = 0; i < N; i++) {
        int sub;
        if (V >= C[i]) {
            sub = 1 + mincoins(C, N, V - C[i]);
            res = min(res, sub);
        }
    }
    return res;
}

int main()
{
    cout << "Enter number of test cases: ";
    int t;
    cin >> t;
    
    while (t--) {
        int N, V;
        
        cout << "Enter the size of Coins array: ";
        cin >> N;
        
        int C[N];
        cout << "Enter the coins: ";
        for (int i = 0; i < N; i++)
            cin >> C[i];
            
        cout << "Enter V (Required sum): ";
        cin >> V;
        
        int res = INT_MAX;
        res = mincoins(C, N, V);
        if (res == INT_MAX or res < 0) {
            cout << "NOT POSSIBLE: ";
            cout << -1;
        }
        else {
            cout << "Required coins: ";
            cout << res << "\n";
        }
    }
    return 0;
}

Output

Enter number of test cases: 3 
Enter the size of Coins array: 3 
Enter the coins: 5 25 10
Enter V (Required sum): 20 
Required coins: 2 
Enter the size of Coins array: 4 
Enter the coins: 9 5 6 1
Enter V (Required sum): 13 
Required coins: 3 
Enter the size of Coins array: 3 
Enter the coins: 7 6 8  
Enter V (Required sum): 9  
NOT POSSIBLE: -1 

Find minimum number of coins that make a given value using dynamic programming approach

Since the same subproblems are called, again and again, this problem has Overlapping Subproblems property.

Like other typical Dynamic Programming (DP) problems, re-computations of the same subproblems can be avoided by constructing a temporary array dp[] and memorizing the computed values in this array.

We will declare a dp[] array of length equal to the sum required+1 since indexing starts from 0, we will use Top-Down DP, use memoization plus recursion approach.

Initially, we will fill the dp[] array with -1 so that during recursion call if the array if not -1 then we don't have to calculate the value we just need to return the dp[value](memoized array), else we will call the function and fill the required value of the array.

Top Down Approach

pseudo code:

int mincoins(coins[],dp[],N,m){
	// where N is the size if coins array and m is the value 
	// of cents for which we are calculating the number of coins.

	if(dp[m]!=-1)	//if we have already solved the subproblem
		return dp[m]	//directly return the memoized value.
	if(m==0)	//base case
		return 0

	res=INT_MAX //initializ the result
	for(i=0;i<N;i++){
		if(coins[i]<=m){
			sub=1+mincoins(coins,dp,m-coins[i])
			//recursive  call				
			if(res>sub)
			res=min(res,sub)	
		}
	}
	dp[m]=res
	return dp[m]	
}

C++ implementation to find minimum number of coins that make a given value using top down approach

#include <bits/stdc++.h>
using namespace std;

int mincoins(int coins[], int N, int dp[], int V)
{
    if (dp[V] != -1)
        return dp[V];
    if (V == 0)
        return 0;
    else {
        int res = 1000000009;
        for (int i = 0; i < N; i++) {
            if (V >= coins[i]) {
                int sub = 1 + mincoins(coins, N, dp, V - coins[i]);
                res = min(res, sub);
            }
        }
        dp[V] = res;
    }
    return dp[V];
}

int main()
{
    int t;
    
    cout << "Enter number of test cases: ";
    cin >> t;
    
    while (t--) {
        int N, V;
        
        cout << "Enter size of coins array: ";
        cin >> N;
        
        int coins[N];
        cout << "Enter coins: ";
        for (int i = 0; i < N; i++)
            cin >> coins[i];
            
        cout << "Enter V (required sum): ";
        cin >> V;
        
        int dp[V + 1];
        for (int i = 0; i <= V; i++)
            dp[i] = -1;
        
        dp[0] = 0;
        dp[V] = mincoins(coins, N, dp, V);
        
        if (dp[V] == 1000000009) {
            cout << "Not Possible: ";
            cout << -1 << "\n";
        }
        else {
            cout << "Required coins: ";
            cout << dp[V] << "\n";
        }
    }
    return 0;
}

Output

Enter number of test cases: 3 
Enter size of coins array: 3  
Enter coins: 5 25 10 
Enter V (required sum): 20 
Required coins: 2 
Enter size of coins array: 4  
Enter coins: 9 5 6 1 
Enter V (required sum): 13 
Required coins: 3 
Enter size of coins array: 3  
Enter coins: 7 6 8
Enter V (required sum): 9  
Not Possible: -1 

2.2) Bottom Up Approach

i^th state of dp : dp[i] : Minimum number of coins required to sum to i cents.

In this approach, we move from the base case to the desired value of the sum
base dp[0]=0 , where for 0 cents of value we need 0 coins.

Initially, we will fill the dp[] array with INT_MAX and dp[0]=0 as for 0 cents we need 0 coins.

Then we will iterate from 1 cent required sum to V value cents.

we will use the outer loop for sum array and inner loop for coins array.

Pseudo Code:

int minCoins(int coins[],int dp[],int N, int V)
{
	// Initializing all values to infinity i.e. minimum coins to make any
	// amount of sum is INT_MAX
	for(i = 0;i<=N;i++)
		dp[i] = INF

	// Base case i.e. minimum coins to make sum = 0 cents is 0
	dp[0] = 0;

	// Iterating in the outer loop for possible values of sum between 1 to V
	// Since our final solution for sum = N might depend upon any of these values
	for(i=1;i<=V;i++){
		// Inner loop denotes the index of coin array.
		// For each value of sum, to obtain the optimal solution.
		for(j = 0;j<N;j++){
			// i —> sum
			// j —> next coin index
			// If we can include this coin in our solution
			if(coins[j] <= i){
				// Solution might include the newly included coin.
				dp[i] = min(dp[i], 1 + dp[i - coins[j]])
			}
		}
	}
	//for(i = 1;i<=N;i++)
	return dp[N];
}

The overall Time complexity of this approach is O(N*V).

C++ implementation to find minimum number of coins that make a given value using bottom up approach

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        int N, V;

        cout << "Enter size of coins array: ";
        cin >> N;

        int coins[N];
        cout << "Enter coins: ";
        for (int i = 0; i < N; i++)
            cin >> coins[i];

        cout << "Enter V (required sum): ";
        cin >> V;
        
        int dp[V + 1];
        for (int i = 0; i <= V; i++)
            dp[i] = 1000000009;
        
        dp[0] = 0;
        
        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < N; j++) {
                if (i >= coins[j]) {
                    dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
                }
            }
        }
        
        if (dp[V] == 1000000009) {
            cout << "Not Possible: ";
            cout << -1 << "\n";
        }
        else {
            cout << "Required coins: ";
            cout << dp[V] << "\n";
        }
    }
    return 0;
}

Output

Enter number of test cases: 3 
Enter size of coins array: 3  
Enter coins: 5 25 10 
Enter V (required sum): 20 
Required coins: 2 
Enter size of coins array: 4  
Enter coins: 9 5 6 1 
Enter V (required sum): 13 
Required coins: 3 
Enter size of coins array: 3  
Enter coins: 7 6 8
Enter V (required sum): 9  
Not Possible: -1