Given a value V, if we want to make a change for V cents, and we have an infinite supply of each of C = { C1, C2, .., Cm} valued coins, what is the minimum number of coins to make the change? If it’s not possible to make a change, print -1.
Examples:
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required We can use one coin of 25 cents and one of 5 centsInput: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required We can use one coin of 6 cents and 1 coin of 5 cents
This problem is a variation of the problem discussed Coin Change Problem. Here instead of finding the total number of possible solutions, we need to find the solution with the minimum number of coins.
The minimum number of coins for a value V can be computed using the below recursive formula.
If V == 0, then 0 coins required.
If V > 0
minCoins(coins[0..m-1], V) = min {1 + minCoins(V-coin[i])}
where i varies from 0 to m-1
and coin[i] <= V
Below is a recursive solution based on the above recursive formula.
C++
// A Naive recursive C++ program to find minimum of coins// to make a given change V#include<bits/stdc++.h>using namespace std;// m is size of coins array (number of different coins)int minCoins(int coins[], int m, int V){ // base case if (V == 0) return 0; // Initialize result int res = INT_MAX; // Try every coin that has smaller value than V for (int i=0; i<m; i++) { if (coins[i] <= V) { int sub_res = minCoins(coins, m, V-coins[i]); // Check for INT_MAX to avoid overflow and see if // result can minimized if (sub_res != INT_MAX && sub_res + 1 < res) res = sub_res + 1; } } return res;}// Driver program to test above functionint main(){ int coins[] = {9, 6, 5, 1}; int m = sizeof(coins)/sizeof(coins[0]); int V = 11; cout << "Minimum coins required is " << minCoins(coins, m, V); return 0;} |
Java
// A Naive recursive JAVA program to find minimum of coins// to make a given change Vimport java.io.*;public class coin{ // m is size of coins array (number of different coins) static int minCoins(int coins[], int m, int V) { // base case if (V == 0) return 0; // Initialize result int res = Integer.MAX_VALUE; // Try every coin that has smaller value than V for (int i=0; i<m; i++) { if (coins[i] <= V) { int sub_res = minCoins(coins, m, V-coins[i]); // Check for INT_MAX to avoid overflow and see if // result can minimized if (sub_res != Integer.MAX_VALUE && sub_res + 1 < res) res = sub_res + 1; } } return res; } public static void main(String args[]) { int coins[] = {9, 6, 5, 1}; int m = coins.length; int V = 11; System.out.println("Minimum coins required is "+ minCoins(coins, m, V) ); }}/* This code is contributed by Rajat Mishra */ |
Python3
# A Naive recursive python program to find minimum of coins# to make a given change Vimport sys# m is size of coins array (number of different coins)def minCoins(coins, m, V): # base case if (V == 0): return 0 # Initialize result res = sys.maxsize # Try every coin that has smaller value than V for i in range(0, m): if (coins[i] <= V): sub_res = minCoins(coins, m, V-coins[i]) # Check for INT_MAX to avoid overflow and see if # result can minimized if (sub_res != sys.maxsize and sub_res + 1 < res): res = sub_res + 1 return res# Driver program to test above functioncoins = [9, 6, 5, 1]m = len(coins)V = 11print("Minimum coins required is",minCoins(coins, m, V))# This code is contributed by# Smitha Dinesh Semwal |
C#
// A Naive recursive C# program// to find minimum of coins// to make a given change Vusing System;class coin{ // m is size of coins array // (number of different coins) static int minCoins(int []coins, int m, int V) { // base case if (V == 0) return 0; // Initialize result int res = int.MaxValue; // Try every coin that has // smaller value than V for (int i = 0; i < m; i++) { if (coins[i] <= V) { int sub_res = minCoins(coins, m, V - coins[i]); // Check for INT_MAX to // avoid overflow and see // if result can minimized if (sub_res != int.MaxValue && sub_res + 1 < res) res = sub_res + 1; } } return res; } // Driver Code public static void Main() { int []coins = {9, 6, 5, 1}; int m = coins.Length; int V = 11; Console.Write("Minimum coins required is "+ minCoins(coins, m, V)); }}// This code is contributed by nitin mittal. |
Javascript
<script>// A Naive recursive Javascript program to// find minimum of coins to make a given // change V // m is size of coins array// (number of different coins)function minCoins(coins, m, V){ // Base case if (V == 0) return 0; // Initialize result let res = Number.MAX_VALUE; // Try every coin that has smaller // value than V for(let i = 0; i < m; i++) { if (coins[i] <= V) { let sub_res = minCoins(coins, m, V - coins[i]); // Check for INT_MAX to avoid overflow and // see if result can minimized if (sub_res != Number.MAX_VALUE && sub_res + 1 < res) res = sub_res + 1; } } return res;}// Driver codelet coins = [ 9, 6, 5, 1 ];let m = coins.length;let V = 11;document.write("Minimum coins required is " + minCoins(coins, m, V) );// This code is contributed by avanitrachhadiya2155</script> |
PHP
<?php// A Naive recursive PHP // program to find minimum // of coins to make a given// change V// m is size of coins array // (number of different coins)function minCoins($coins, $m, $V){ // base caseif ($V == 0) return 0;// Initialize result$res = PHP_INT_MAX;// Try every coin that has// smaller value than Vfor ($i = 0; $i < $m; $i++){ if ($coins[$i] <= $V) { $sub_res = minCoins($coins, $m, $V - $coins[$i]); // Check for INT_MAX to // avoid overflow and see // if result can minimized if ($sub_res != PHP_INT_MAX && $sub_res + 1 < $res) $res = $sub_res + 1; }}return $res;}// Driver Code$coins = array(9, 6, 5, 1);$m = sizeof($coins);$V = 11;echo "Minimum coins required is ", minCoins($coins, $m, $V); // This code is contributed by ajit?> |
Output
Minimum coins required is 2
The time complexity of the above solution is exponential and space complexity is way greater than O(n). If we draw the complete recursion tree, we can observe that many subproblems are solved again and again. For example, when we start from V = 11, we can reach 6 by subtracting one 5 times and by subtracting 5 one time. So the subproblem for 6 is called twice.
Since the same subproblems are called again, this problem has the Overlapping Subproblems property. So the min coins problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of the same subproblems can be avoided by constructing a temporary array table[][] in a bottom-up manner. Below is Dynamic Programming based solution.
C++
// A Dynamic Programming based C++ program to find minimum// of coins to make a given change V#include <bits/stdc++.h>using namespace std;// m is size of coins array (number of different coins)int minCoins(int coins[], int m, int V){ // table[i] will be storing the minimum number of coins // required for i value. So table[V] will have result int table[V + 1]; // Base case (If given value V is 0) table[0] = 0; // Initialize all table values as Infinite for (int i = 1; i <= V; i++) table[i] = INT_MAX; // Compute minimum coins required for all // values from 1 to V for (int i = 1; i <= V; i++) { // Go through all coins smaller than i for (int j = 0; j < m; j++) if (coins[j] <= i) { int sub_res = table[i - coins[j]]; if (sub_res != INT_MAX && sub_res + 1 < table[i]) table[i] = sub_res + 1; } } if (table[V] == INT_MAX) return -1; return table[V];}// Driver program to test above functionint main(){ int coins[] = { 9, 6, 5, 1 }; int m = sizeof(coins) / sizeof(coins[0]); int V = 11; cout << "Minimum coins required is " << minCoins(coins, m, V); return 0;} |
Java
// A Dynamic Programming based Java// program to find minimum of coins// to make a given change Vimport java.io.*;class GFG { // m is size of coins array // (number of different coins) static int minCoins(int coins[], int m, int V) { // table[i] will be storing // the minimum number of coins // required for i value. So // table[V] will have result int table[] = new int[V + 1]; // Base case (If given value V is 0) table[0] = 0; // Initialize all table values as Infinite for (int i = 1; i <= V; i++) table[i] = Integer.MAX_VALUE; // Compute minimum coins required for all // values from 1 to V for (int i = 1; i <= V; i++) { // Go through all coins smaller than i for (int j = 0; j < m; j++) if (coins[j] <= i) { int sub_res = table[i - coins[j]]; if (sub_res != Integer.MAX_VALUE && sub_res + 1 < table[i]) table[i] = sub_res + 1; } } if(table[V]==Integer.MAX_VALUE) return -1; return table[V]; } // Driver program public static void main (String[] args) { int coins[] = {9, 6, 5, 1}; int m = coins.length; int V = 11; System.out.println ( "Minimum coins required is " + minCoins(coins, m, V)); }}//This Code is contributed by vt_m. |
Python3
# A Dynamic Programming based Python3 program to # find minimum of coins to make a given change Vimport sys # m is size of coins array (number of # different coins)def minCoins(coins, m, V): # table[i] will be storing the minimum # number of coins required for i value. # So table[V] will have result table = [0 for i in range(V + 1)] # Base case (If given value V is 0) table[0] = 0 # Initialize all table values as Infinite for i in range(1, V + 1): table[i] = sys.maxsize # Compute minimum coins required # for all values from 1 to V for i in range(1, V + 1): # Go through all coins smaller than i for j in range(m): if (coins[j] <= i): sub_res = table[i - coins[j]] if (sub_res != sys.maxsize and sub_res + 1 < table[i]): table[i] = sub_res + 1 if table[V] == sys.maxsize: return -1 return table[V]# Driver Codeif __name__ == "__main__": coins = [9, 6, 5, 1] m = len(coins) V = 11 print("Minimum coins required is ", minCoins(coins, m, V))# This code is contributed by ita_c |
C#
// A Dynamic Programming based // Java program to find minimum // of coins to make a given // change Vusing System;class GFG{// m is size of coins array // (number of different coins)static int minCoins(int []coins, int m, int V){ // table[i] will be storing // the minimum number of coins // required for i value. So // table[V] will have result int []table = new int[V + 1]; // Base case (If given // value V is 0) table[0] = 0; // Initialize all table // values as Infinite for (int i = 1; i <= V; i++) table[i] = int.MaxValue; // Compute minimum coins // required for all // values from 1 to V for (int i = 1; i <= V; i++) { // Go through all coins // smaller than i for (int j = 0; j < m; j++) if (coins[j] <= i) { int sub_res = table[i - coins[j]]; if (sub_res != int.MaxValue && sub_res + 1 < table[i]) table[i] = sub_res + 1; } } return table[V]; }// Driver Code static public void Main (){ int []coins = {9, 6, 5, 1}; int m = coins.Length; int V = 11; Console.WriteLine("Minimum coins required is " + minCoins(coins, m, V));}}// This code is contributed // by akt_mit |
Javascript
<script>// A Dynamic Programming based Javascript// program to find minimum of coins// to make a given change V // m is size of coins array // (number of different coins) function minCoins(coins,m,v) { // table[i] will be storing // the minimum number of coins // required for i value. So // table[V] will have result let table = new Array(V+1); // Initialize first table value as zero table[0] = 0; // Initialize all table values as Infinite except for the first one for (let i = 1; i <= V; i++) { table[i] = Number.MAX_VALUE; } // Compute minimum coins required for all // values from 1 to V for (let i = 1; i <= V; i++) { // Go through all coins smaller than i for (let j = 0; j < m; j++) if (coins[j] <= i) { let sub_res = table[i - coins[j]]; if (sub_res != Number.MAX_VALUE && sub_res + 1 < table[i]) table[i] = sub_res + 1; } } if(table[V] == Number.MAX_VALUE) return -1; return table[V]; } // Driver program let coins = [9, 6, 5, 1]; let m = coins.length; let V = 11; document.write( "Minimum coins required is " + minCoins(coins, m, V)) // This code is contributed by rag2127</script> |
PHP
<?php// A Dynamic Programming based // PHP program to find minimum // of coins to make a given // change V.// m is size of coins // array (number of different coins)function minCoins($coins, $m, $V){ // table[i] will be storing the // minimum number of coins // required for i value. So // table[V] will have result $table[$V + 1] = array(); // Base case (If given // value V is 0) $table[0] = 0; // Initialize all table // values as Infinite for ($i = 1; $i <= $V; $i++) $table[$i] = PHP_INT_MAX; // Compute minimum coins // required for all // values from 1 to V for ($i = 1; $i <= $V; $i++) { // Go through all coins // smaller than i for ($j = 0; $j < $m; $j++) if ($coins[$j] <= $i) { $sub_res = $table[$i - $coins[$j]]; if ($sub_res != PHP_INT_MAX && $sub_res + 1 < $table[$i]) $table[$i] = $sub_res + 1; } } if ($table[$V] == PHP_INT_MAX) return -1; return $table[$V];}// Driver Code$coins = array(9, 6, 5, 1);$m = sizeof($coins);$V = 11;echo "Minimum coins required is ", minCoins($coins, $m, $V);// This code is contributed by ajit?> |
Output
Minimum coins required is 2
Time complexity: O(m*V).
Auxiliary space: O(V) because using extra space for array table
Coin change using the Top Down (Memoization) Dynamic Programming:
The idea is to find the Number of ways of Denominations By using the Top Down (Memoization).
Follow the below steps to Implement the idea:
- Creating a 2-D vector to store the Overlapping Solutions
- Keep Track of the overlapping subproblems while Traversing the array coins[]
- Recall them whenever needed.
Below is the implementation using the Top Down Memoized Approach
C++
#include <bits/stdc++.h>using namespace std;// Utility function for solving the minimum coins problemint minCoinsUtil(int coins[], int m, int V, int* dp){ // Base case: If target value V is 0, no coins are // needed if (V == 0) return 0; // If subproblem is already solved, return the result // from DP table if (dp[V] != -1) return dp[V]; int res = INT_MAX; // Iterate over all coins and recursively solve for // subproblems for (int i = 0; i < m; i++) { if (coins[i] <= V) { // Recursive call to solve for remaining value V // - coins[i] int sub_res = minCoinsUtil(coins, m, V - coins[i], dp); // If the subproblem has a valid solution and // the total number of coins is smaller than the // current result, update the result if (sub_res != INT_MAX && sub_res + 1 < res) res = sub_res + 1; } } // Save the result in the DP table dp[V] = res; return res;}// Function to find the minimum number of coins needed to// make a target valueint minCoins(int coins[], int m, int V){ // Create a DP table to store results of subproblems int* dp = new int[V + 1]; memset(dp, -1, sizeof(int) * (V + 1)); // Initialize DP table with -1 // Call the utility function to solve the problem return minCoinsUtil(coins, m, V, dp);}// Driver codeint main(){ int coins[] = { 9, 6, 5, 1 }; int m = sizeof(coins) / sizeof(coins[0]); int V = 11; int res = minCoins(coins, m, V); if (res == INT_MAX) res = -1; // Find the minimum number of coins required cout << "Minimum coins required is " << res; return 0;} |
Java
import java.util.Arrays;public class MinimumCoins { // Utility function for solving the minimum coins // problem public static int minCoinsUtil(int[] coins, int m, int V, int[] dp) { // Base case: If target value V is 0, no coins are // needed if (V == 0) return 0; // If subproblem is already solved, return the // result from DP table if (dp[V] != -1) return dp[V]; int res = Integer.MAX_VALUE; // Iterate over all coins and recursively solve for // subproblems for (int i = 0; i < m; i++) { if (coins[i] <= V) { // Recursive call to solve for remaining // value V - coins[i] int sub_res = minCoinsUtil( coins, m, V - coins[i], dp); // If the subproblem has a valid solution // and the total number of coins is smaller // than the current result, update the // result if (sub_res != Integer.MAX_VALUE && sub_res + 1 < res) res = sub_res + 1; } } // Save the result in the DP table dp[V] = res; return res; } // Function to find the minimum number of coins needed // to make a target value public static int minCoins(int[] coins, int m, int V) { // Create a DP table to store results of subproblems int[] dp = new int[V + 1]; Arrays.fill(dp, -1); // Initialize DP table with -1 // Call the utility function to solve the problem return minCoinsUtil(coins, m, V, dp); } // Driver code public static void main(String[] args) { int[] coins = { 9, 6, 5, 1 }; int m = coins.length; int V = 11; int res = minCoins(coins, m, V); if (res == Integer.MAX_VALUE) res = -1; // Find the minimum number of coins required System.out.println("Minimum coins required is " + res); }} |
Python3
import sys# Utility function for solving the minimum coins problemdef minCoinsUtil(coins, m, V, dp): # Base case: If target value V is 0, no coins are needed if V == 0: return 0 # If subproblem is already solved, return the result from DP table if dp[V] != -1: return dp[V] res = sys.maxsize # Iterate over all coins and recursively solve for subproblems for i in range(m): if coins[i] <= V: # Recursive call to solve for remaining value V - coins[i] sub_res = minCoinsUtil(coins, m, V - coins[i], dp) # If the subproblem has a valid solution and the total number of coins # is smaller than the current result, update the result if sub_res != sys.maxsize and sub_res + 1 < res: res = sub_res + 1 # Save the result in the DP table dp[V] = res return res# Function to find the minimum number of coins needed to make a target valuedef minCoins(coins, m, V): # Create a DP table to store results of subproblems dp = [-1] * (V + 1) # Call the utility function to solve the problem return minCoinsUtil(coins, m, V, dp)# Driver codeif __name__ == "__main__": coins = [9, 6, 5, 1] m = len(coins) V = 11 res = minCoins(coins, m, V) if res == sys.maxsize: res = -1 # Find the minimum number of coins required print("Minimum coins required is", res) |
C#
using System; class MinimumCoinChange { static int minCoinsUtil(int[] coins, int m, int V, int[] dp) { // Base case: If target value V is 0, no coins are // needed if (V == 0) return 0; // If subproblem is already solved, return the result // from DP table if (dp[V] != -1) return dp[V]; int res = int.MaxValue; // Iterate over all coins and recursively solve for // subproblems for (int i = 0; i < m; i++) { if (coins[i] <= V) { // Recursive call to solve for remaining value V // - coins[i] int sub_res = minCoinsUtil(coins, m, V - coins[i], dp); // If the subproblem has a valid solution and // the total number of coins is smaller than the // current result, update the result if (sub_res != int.MaxValue && sub_res + 1 < res) res = sub_res + 1; } } // Save the result in the DP table dp[V] = res; return res; } static int minCoins(int[] coins, int m, int V) { // Create a DP table to store results of subproblems int[] dp = new int[V + 1]; Array.Fill(dp, -1); // Initialize DP table with -1 // Call the utility function to solve the problem return minCoinsUtil(coins, m, V, dp); } static void Main(string[] args) { int[] coins = { 9, 6, 5, 1 }; int m = coins.Length; int V = 11; int res = minCoins(coins, m, V); if (res == int.MaxValue) res = -1; // Find the minimum number of coins required Console.WriteLine("Minimum coins required is " + res); Console.ReadLine(); }} |
Javascript
function minCoinsUtil(coins, m, V, dp) { if (V === 0) { return 0; } if (dp[V] !== -1) { return dp[V]; } let res = Infinity; for (let i = 0; i < m; i++) { if (coins[i] <= V) { let sub_res = minCoinsUtil(coins, m, V - coins[i], dp); if (sub_res !== Infinity && sub_res + 1 < res) { res = sub_res + 1; } } } dp[V] = res; return res;}function minCoins(coins, m, V) { const dp = new Array(V + 1).fill(-1); return minCoinsUtil(coins, m, V, dp);}const coins = [9, 6, 5, 1];const m = coins.length;const V = 11;const res = minCoins(coins, m,V);if(res == Infinity) res = -1;console.log("Minimum coins required is", res); |
Output
Minimum coins required is 2
Time Complexity: O(m * V)
Auxiliary Space: (V)
Thanks to Goku for suggesting the above solution in a comment here and thanks to Vignesh Mohan for suggesting this problem and initial solution.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
