Home » Interview coding problems/challenges

# Minimum Coin Change | 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.

Submitted by Divyansh Jaipuriyar, on April 23, 2020

**Problem statement:**

Given a value * V*, if we want to make change for

*cents, and we have infinite supply of each of*

**V***valued coins, what is the minimum number of coins to make the change?*

**C = { C1, C2, .. , Cm}****Input:**

The test case consists of * V* and

*,*

**N***is the value of cents and*

**V***is the number of coins. The second line of each test case contains*

**N***input*

**N***, the value of available coins.*

**C[i]****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

**Solution Approach**

**1) 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

*coin and decrease the sum*

**{C1, C2, ..., CN}***.*

**V**By * C[i] *(based on the coin we took). Whenever

*becomes 0, this means we have a possible or otherwise there is no solution and we return -1;*

**V****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,

*is the size of the coin array and*

**N***is the required sum.*

**V**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:**

#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

**2) 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

*(memoized array), else we will call the function and fill the required value of the array.*

**dp[value]****2.1) 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:**

#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***: Minimum number of coins required to sum to*

**dp[i]***cents.*

**i**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

*and*

**INT_MAX***as for 0 cents we need 0 coins.*

**dp[0]=0**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:**

#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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.