Minimum coins
Dynamic Programming
DP on subsequences
Hard
Given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that are needed to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. There are infinite numbers of coins of each type
Examples:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1. We need 3 coins to make up the amount 11.
Input: coins = [2, 5], amount = 3
Output: -1
Explanation: It's not possible to make amount 3 with coins 2 and 5. Since we can't combine the coin 2 and 5 to make the amount 3, the output is -1.
Input: coins = [1], amount = 0
Constraints
- n=number of distinct denominations
- 1 <= n <= 100
- 1 <= coins[i], amount <= 103
Hints
- "Define dp[i] as the minimum number of coins needed to make up amount i. the recurrence relation is: dp[i]=min(dp[i],dp[i−coin]+1)for each coin"
- Since dp[i] only depends on smaller values, we only need a 1D DP array (dp[amount]) instead of O(n × amount).
Company Tags
Ubisoft
Wayfair
Instacart
Mastercard
Ernst & Young
DoorDash
Lyft
Texas Instruments
Roche
Activision Blizzard
HCL Technologies
Databricks
Twilio
Rockstar Games
Intel
McKinsey & Company
Dropbox
Siemens Healthineers
Robinhood
Alibaba
Bungie
Byju's
Zynga
Zoho
Etsy
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Why a Greedy Solution will not work:
As the question asks for minimum number of coins, the first approach that comes to our mind is greedy. A greedy solution will fail in this problem because there is no ‘uniformity’ in data. While selecting a local better choice we may choose an item that will in the long term give less value.
A Greedy solution will be to take the highest denomination coin first, so we will take an item on index 0, with a value of 9. Now the remaining target sum will be 2. Therefore we can only consider coins with a value of 1. We will take 2 coins of value 1 to meet the target. So a greedy solution gives us the answer 3 (9,1,1).
Now we can clearly see that a non-greedy solution of taking 2 coins (6,5) gives a better option. So we can say that the greedy solution doesn’t work for this problem.
As the greedy approach doesn’t work, try to generate all possible combinations using recursion and select the combination which gives the minimum number of coins.
Steps to form the recursive solution:
- Express the problem in terms of indexes:We are given ‘n’ distinct numbers, where n is the length of the array. Their denomination is represented by the ‘coins’ array. So clearly one parameter will be ‘ind’, i.e index up to which the array items are being considered. There is one more parameter “T”, to know the given target that we want to achieve.
- Try out all possible choices at a given index:As all the subsets needs to be generated, use the pick/non-pick technique. There will be a slight change for this question which is discussed below.
- Return the minimum of two choices:As we have to return the minimum number of coins, we will return the minimum of take and notTake as our answer.
- Base Case:If ind==0, it means we are at the first item, so in that case, the following cases can arise:
In cases where the target is divisible by the coin element, return (T / arr[0]), as this will give the number of coins needed to make target.
In all other cases, where the target is not divisible by the coin, a solution can not be formed, so return a big number like 1e9. This will prevent the coin from getting added to the final solution as we need to reutrn the minimum number of coins.
So, initially, we need to find f(n-1, T) where T is the initial target given. f(n-1, T) will give the minimum number of coins required to form the target sum by considering coins from index 0 to n-1.
We have two choices:
Exclude the current element in the subset: First try to find a subset without considering the current index coin. If the current coin is excluded, the target sum will not be affected and the number of coins added to the solution will be 0. So call the recursive function f(ind-1, T).
Include the current element in the subset: Try to find a subset by considering the current icoin. As the current coin is included, the target sum will be updated to T-arr[ind], as we have considered 1 coin to be part of the solution.
Now here is the catch, as there is an unlimited supply of coins, we want to again form a solution with the same coin value. So we will not recursively call for f(ind-1, T-arr[ind]) rather we will stay at that index only and call for f(ind, T-arr[ind]) to find the answer.
Note: Consider the current coin only when its denomination value (arr[ind]) is less than or equal to the target T.
1234
f(ind, T){
notTake = 0 + f(ind-1, T)
take = 1e9
if(arr[ind] <= T)
take = 1 + f(ind, T-arr[ind])
}1234
f(ind, T){
notTake = 0 + f(ind-1, T)
take = 1e9
if(arr[ind] <= T)
take = 1 + f(ind, T-arr[ind])
return min(take, notTake)
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
#include <bits/stdc++.h>
using namespace std;
class Solution{
const int mod = (int)1e9 + 7;
private:
/* Function to calculate the minimum number
of elements to form the target sum*/
int func(vector<int>& arr, int ind, int T){
// Base case: If we're at the first element
if(ind == 0){
/* Check if the target sum is
divisible by the first element*/
if(T % arr[0] == 0)
return T / arr[0];
else
/* Otherwise, return a very large
value to indicate it's not possible*/
return 1e9;
}
/* Calculate the minimum elements needed
without taking the current element*/
int notTaken = 0 + func(arr, ind - 1, T);
/* Calculate the minimum elements
needed by taking the current element*/
int taken = 1e9;
if(arr[ind] <= T)
taken = 1 + func(arr, ind, T - arr[ind]);
// Return minimum of 'notTaken' and 'taken'
return min(notTaken, taken);
}
public:
/* Function to find the minimum number
of coins needed to form the target sum*/
int minimumCoins(vector<int>& coins, int amount){
int n = coins.size();
// Call utility function to calculate the answer
int ans = func(coins, n - 1, amount);
/* If 'ans' is still very large, it means
mean it's not possible to form the target sum*/
if(ans >= 1e9)
return -1;
// Return the minimum number of coins
return ans;
}
};
int main() {
vector<int> coins = {1, 2, 3};
int amount = 7;
//Create an instance of Solution class
Solution sol;
// Print the result
cout << "The total number of ways is " << sol.minimumCoins(coins, amount) << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
import java.util.*;
class Solution {
final int mod = (int)1e9 + 7;
/* Function to calculate the minimum number
of elements to form the target sum */
private int func(int[] arr, int ind, int T) {
// Base case: If we're at the first element
if (ind == 0) {
/* Check if the target sum is
divisible by the first element */
if (T % arr[0] == 0)
return T / arr[0];
else
/* Otherwise, return a very large
value to indicate it's not possible */
return (int)1e9;
}
/* Calculate the minimum elements needed
without taking the current element */
int notTaken = func(arr, ind - 1, T);
/* Calculate the minimum elements
needed by taking the current element */
int taken = (int)1e9;
if (arr[ind] <= T)
taken = 1 + func(arr, ind, T - arr[ind]);
// Return minimum of 'notTaken' and 'taken'
return Math.min(notTaken, taken);
}
/* Function to find the minimum number
of coins needed to form the target sum */
public int minimumCoins(int[] coins, int amount) {
int n = coins.length;
// Call utility function to calculate the answer
int ans = func(coins, n - 1, amount);
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= (int)1e9)
return -1;
// Return the minimum number of coins
return ans;
}
public static void main(String[] args) {
int[] coins = {1, 2, 3};
int amount = 7;
// Create an instance of Solution class
Solution sol = new Solution();
// Print the result
System.out.println("The total number of ways is " + sol.minimumCoins(coins, amount));
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
class Solution:
mod = int(1e9) + 7
""" Function to calculate the minimum number
of elements to form the target sum """
def func(self, arr, ind, T):
# Base case: If we're at the first element
if ind == 0:
""" Check if the target sum is
divisible by the first element"""
if T % arr[0] == 0:
return T // arr[0]
else:
""" Otherwise, return a very large
value to indicate it's not possible"""
return int(1e9)
""" Calculate the minimum elements needed
without taking the current element"""
not_taken = self.func(arr, ind - 1, T)
""" Calculate the minimum elements
needed by taking the current element"""
taken = int(1e9)
if arr[ind] <= T:
taken = 1 + self.func(arr, ind, T - arr[ind])
# Return minimum of 'notTaken' and 'taken'
return min(not_taken, taken)
""" Function to find the minimum number
of coins needed to form the target sum"""
def minimumCoins(self, coins, amount):
n = len(coins)
# Call utility function to calculate the answer
ans = self.func(coins, n - 1, amount)
""" If 'ans' is still very large, it means
it's not possible to form the target sum"""
if ans >= int(1e9):
return -1
# Return the minimum number of coins
return ans
coins = [1, 2, 3]
amount = 7
# Create an instance of Solution class
sol = Solution()
# Print the result
print("The total number of ways is", sol.minimumCoins(coins, amount))
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
class Solution {
constructor() {
this.mod = 1e9 + 7;
}
/* Function to calculate the minimum number
of elements to form the target sum */
func(arr, ind, T) {
// Base case: If we're at the first element
if (ind === 0) {
/* Check if the target sum is
divisible by the first element */
if (T % arr[0] === 0)
return T / arr[0];
else
/* Otherwise, return a very large
value to indicate it's not possible */
return 1e9;
}
/* Calculate the minimum elements needed
without taking the current element */
let notTaken = this.func(arr, ind - 1, T);
/* Calculate the minimum elements
needed by taking the current element */
let taken = 1e9;
if (arr[ind] <= T)
taken = 1 + this.func(arr, ind, T - arr[ind]);
/* Store the minimum of 'notTaken' and
'taken' in the DP array and return it */
return Math.min(notTaken, taken);
}
/* Function to find the minimum number
of coins needed to form the target sum */
minimumCoins(coins, amount) {
const n = coins.length;
// Call utility function to calculate the answer
const ans = this.func(coins, n - 1, amount);
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= 1e9)
return -1;
// Return the minimum number of coins
return ans;
}
}
const coins = [1, 2, 3];
const amount = 7;
// Create an instance of Solution class
const sol = new Solution();
// Print the result
console.log("The total number of ways is " + sol.minimumCoins(coins, amount));
Complexity Analysis:
Time Complexity:O(2N), as each element has 2 choices, and there are N elements in the array.Space Complexity:O(N), the stack space will be O(N), the maximum depth of the stack.
If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.
In order to convert a recursive solution to memoization the following steps will be taken:
- Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.
- While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
- Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.
The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
#include <bits/stdc++.h>
using namespace std;
class Solution{
const int mod = (int)1e9 + 7;
private:
/* Function to calculate the minimum number
of elements to form the target sum*/
int func(vector<int>& arr, int ind, int T, vector<vector<int>>& dp){
// Base case: If we're at the first element
if(ind == 0){
/* Check if the target sum is
divisible by the first element*/
if(T % arr[0] == 0)
return T / arr[0];
else
/* Otherwise, return a very large
value to indicate it's not possible*/
return 1e9;
}
/* If the result for this index and target
sum is already calculated, return it*/
if(dp[ind][T] != -1)
return dp[ind][T];
/* Calculate the minimum elements needed
without taking the current element*/
int notTaken = 0 + func(arr, ind - 1, T, dp);
/* Calculate the minimum elements
needed by taking the current element*/
int taken = 1e9;
if(arr[ind] <= T)
taken = 1 + func(arr, ind, T - arr[ind], dp);
/* Store the minimum of 'notTaken' and
'taken' in the DP array and return it*/
return dp[ind][T] = min(notTaken, taken);
}
public:
/* Function to find the minimum number
of coins needed to form the target sum*/
int minimumCoins(vector<int>& coins, int amount){
int n = coins.size();
/* Create a DP (Dynamic Programming) table with
n rows and amount+1 columns and initialize it with -1*/
vector<vector<int>> dp(n, vector<int>(amount + 1, -1));
// Call utility function to calculate the answer
int ans = func(coins, n - 1, amount, dp);
/* If 'ans' is still very large, it means
mean it's not possible to form the target sum*/
if(ans >= 1e9)
return -1;
// Return the minimum number of coins
return ans;
}
};
int main() {
vector<int> coins = {1, 2, 3};
int amount = 7;
//Create an instance of Solution class
Solution sol;
// Print the result
cout << "The total number of ways is " << sol.minimumCoins(coins, amount) << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
import java.util.*;
class Solution {
final int mod = (int)1e9 + 7;
/* Function to calculate the minimum number
of elements to form the target sum */
private int func(int[] arr, int ind, int T, int[][] dp) {
// Base case: If we're at the first element
if (ind == 0) {
/* Check if the target sum is
divisible by the first element */
if (T % arr[0] == 0)
return T / arr[0];
else
/* Otherwise, return a very large
value to indicate it's not possible */
return (int)1e9;
}
/* If the result for this index and target
sum is already calculated, return it */
if (dp[ind][T] != -1)
return dp[ind][T];
/* Calculate the minimum elements needed
without taking the current element */
int notTaken = func(arr, ind - 1, T, dp);
/* Calculate the minimum elements
needed by taking the current element */
int taken = (int)1e9;
if (arr[ind] <= T)
taken = 1 + func(arr, ind, T - arr[ind], dp);
/* Store the minimum of 'notTaken' and
'taken' in the DP array and return it */
return dp[ind][T] = Math.min(notTaken, taken);
}
/* Function to find the minimum number
of coins needed to form the target sum */
public int minimumCoins(int[] coins, int amount) {
int n = coins.length;
/* Create a DP (Dynamic Programming) table with
n rows and amount+1 columns and initialize it with -1 */
int[][] dp = new int[n][amount + 1];
for (int[] row : dp)
Arrays.fill(row, -1);
// Call utility function to calculate the answer
int ans = func(coins, n - 1, amount, dp);
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= (int)1e9)
return -1;
// Return the minimum number of coins
return ans;
}
public static void main(String[] args) {
int[] coins = {1, 2, 3};
int amount = 7;
// Create an instance of Solution class
Solution sol = new Solution();
// Print the result
System.out.println("The total number of ways is " + sol.minimumCoins(coins, amount));
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
class Solution:
mod = int(1e9) + 7
""" Function to calculate the minimum number
of elements to form the target sum """
def func(self, arr, ind, T, dp):
# Base case: If we're at the first element
if ind == 0:
""" Check if the target sum is
divisible by the first element"""
if T % arr[0] == 0:
return T // arr[0]
else:
""" Otherwise, return a very large
value to indicate it's not possible"""
return int(1e9)
""" If the result for this index and target
sum is already calculated, return it"""
if dp[ind][T] != -1:
return dp[ind][T]
""" Calculate the minimum elements needed
without taking the current element"""
not_taken = self.func(arr, ind - 1, T, dp)
""" Calculate the minimum elements
needed by taking the current element"""
taken = int(1e9)
if arr[ind] <= T:
taken = 1 + self.func(arr, ind, T - arr[ind], dp)
""" Store the minimum of 'not_taken' and
'taken' in the DP array and return it"""
dp[ind][T] = min(not_taken, taken)
return dp[ind][T]
""" Function to find the minimum number
of coins needed to form the target sum"""
def minimumCoins(self, coins, amount):
n = len(coins)
""" Create a DP (Dynamic Programming) table with n
rows and amount+1 columns and initialize it with -1"""
dp = [[-1] * (amount + 1) for _ in range(n)]
# Call utility function to calculate the answer
ans = self.func(coins, n - 1, amount, dp)
""" If 'ans' is still very large, it means
it's not possible to form the target sum"""
if ans >= int(1e9):
return -1
# Return the minimum number of coins
return ans
coins = [1, 2, 3]
amount = 7
# Create an instance of Solution class
sol = Solution()
# Print the result
print("The total number of ways is", sol.minimumCoins(coins, amount))
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
class Solution {
constructor() {
this.mod = 1e9 + 7;
}
/* Function to calculate the minimum number
of elements to form the target sum */
func(arr, ind, T, dp) {
// Base case: If we're at the first element
if (ind === 0) {
/* Check if the target sum is
divisible by the first element */
if (T % arr[0] === 0)
return T / arr[0];
else
/* Otherwise, return a very large
value to indicate it's not possible */
return 1e9;
}
/* If the result for this index and target
sum is already calculated, return it */
if (dp[ind][T] !== -1)
return dp[ind][T];
/* Calculate the minimum elements needed
without taking the current element */
let notTaken = this.func(arr, ind - 1, T, dp);
/* Calculate the minimum elements
needed by taking the current element */
let taken = 1e9;
if (arr[ind] <= T)
taken = 1 + this.func(arr, ind, T - arr[ind], dp);
/* Store the minimum of 'notTaken' and
'taken' in the DP array and return it */
dp[ind][T] = Math.min(notTaken, taken);
return dp[ind][T];
}
/* Function to find the minimum number
of coins needed to form the target sum */
minimumCoins(coins, amount) {
const n = coins.length;
/* Create a DP (Dynamic Programming) table with
n rows and amount+1 columns and initialize it with -1 */
const dp = Array.from({ length: n }, () => Array(amount + 1).fill(-1));
// Call utility function to calculate the answer
const ans = this.func(coins, n - 1, amount, dp);
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= 1e9)
return -1;
// Return the minimum number of coins
return ans;
}
}
const coins = [1, 2, 3];
const amount = 7;
// Create an instance of Solution class
const sol = new Solution();
// Print the result
console.log("The total number of ways is " + sol.minimumCoins(coins, amount));
Complexity Analysis:
Time Complexity:O(N*Target), as there are N*Target states therefore at max ‘N*Target’ new problems will be solved.Space Complexity:O(N*Target) + O(N), the stack space will be O(N) and a 2D array of size N*T is used.
In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:
- Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n) and including 0 its n, where n is the size of array, for 'target' can have any values between 0 to 'target'. So we need a 2D dp array. Set its type as int and initialize it as 0.
- Setting Base Cases in the Array: In the recursive code, our base condition was when 'ind' == 0, it means we were considering the first element. So for 'ind' == 0, if T%arr[0] ==0, initialize the dp array to T/arr[0] else initialize it to 1e9.
- Iterative Computation Using Loops: As we are done for the first row(ind = 0) in the base case, so ‘ind’ variable will move from 1 to n-1, whereas ‘target’ variable will move from 0 to 'T'(target). Initialize two nested for loops to traverse the dp array and following the logic discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations.
- Returning the answer: At last dp[n-1][target] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
#include <bits/stdc++.h>
using namespace std;
class Solution{
public:
/* Function to find the minimum number
of elements needed to form the target sum*/
int minimumCoins(vector<int>& coins, int amount) {
int n = coins.size();
/* Create a 2D DP table with
n rows and amount+1 columns*/
vector<vector<int>> dp(n, vector<int>(amount + 1, 0));
// Initialize the first row of the DP table
for (int i = 0; i <= amount; i++) {
if (i % coins[0] == 0)
dp[0][i] = i / coins[0];
else
dp[0][i] = 1e9;
}
// Fill the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
for (int target = 0; target <= amount; target++) {
/* Calculate the minimum elements needed
without taking the current element*/
int notTake = dp[ind - 1][target];
/* Calculate the minimum elements
needed by taking the current element*/
int take = 1e9;
if (coins[ind] <= target)
take = 1 + dp[ind][target - coins[ind]];
/* Store the minimum of 'notTake'
and 'take' in the DP table*/
dp[ind][target] = min(notTake, take);
}
}
// The answer is in the bottom-right cell
int ans = dp[n - 1][amount];
/* If 'ans' is still very large, it means
it's not possible to form the target sum*/
if (ans >= 1e9)
return -1;
// Return the minimum number of coins needed
return ans;
}
};
int main() {
vector<int> coins = {1, 2, 3};
int amount = 7;
//Create an instance of Solution class
Solution sol;
// Call the function to find the minimum coins
int result = sol.minimumCoins(coins, amount);
// Output the result
cout << "The minimum number of coins required to form the target sum is " << result << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
import java.util.*;
class Solution {
/* Function to find the minimum number
of elements needed to form the target sum */
public int minimumCoins(int[] coins, int amount) {
int n = coins.length;
/* Create a 2D DP table with
n rows and amount+1 columns */
int[][] dp = new int[n][amount + 1];
// Initialize the first row of the DP table
for (int i = 0; i <= amount; i++) {
if (i % coins[0] == 0)
dp[0][i] = i / coins[0];
else
dp[0][i] = (int)1e9;
}
// Fill the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
for (int target = 0; target <= amount; target++) {
/* Calculate the minimum elements needed
without taking the current element */
int notTake = dp[ind - 1][target];
/* Calculate the minimum elements
needed by taking the current element */
int take = (int)1e9;
if (coins[ind] <= target)
take = 1 + dp[ind][target - coins[ind]];
/* Store the minimum of 'notTake'
and 'take' in the DP table */
dp[ind][target] = Math.min(notTake, take);
}
}
// The answer is in the bottom-right cell
int ans = dp[n - 1][amount];
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= (int)1e9)
return -1;
// Return the minimum number of coins needed
return ans;
}
public static void main(String[] args) {
int[] coins = {1, 2, 3};
int amount = 7;
// Create an instance of Solution class
Solution sol = new Solution();
// Call the function to find the minimum coins
int result = sol.minimumCoins(coins, amount);
// Output the result
System.out.println("The minimum number of coins required to form the target sum is " + result);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
class Solution:
""" Function to find the minimum number
of elements needed to form the target sum """
def minimumCoins(self, coins, amount):
n = len(coins)
""" Create a 2D DP table with
n rows and amount+1 columns """
dp = [[0] * (amount + 1) for _ in range(n)]
# Initialize the first row of the DP table
for i in range(amount + 1):
if i % coins[0] == 0:
dp[0][i] = i // coins[0]
else:
dp[0][i] = int(1e9)
# Fill the DP table using a bottom-up approach
for ind in range(1, n):
for target in range(amount + 1):
""" Calculate the minimum elements needed
without taking the current element """
notTake = dp[ind - 1][target]
""" Calculate the minimum elements
needed by taking the current element """
take = int(1e9)
if coins[ind] <= target:
take = 1 + dp[ind][target - coins[ind]]
""" Store the minimum of 'notTake'
and 'take' in the DP table """
dp[ind][target] = min(notTake, take)
# The answer is in the bottom-right cell
ans = dp[n - 1][amount]
""" If 'ans' is still very large, it means
it's not possible to form the target sum """
if ans >= int(1e9):
return -1
# Return the minimum number of coins needed
return ans
coins = [1, 2, 3]
amount = 7
# Create an instance of Solution class
sol = Solution()
# Call the function to find the minimum coins
result = sol.minimumCoins(coins, amount)
# Output the result
print("The minimum number of coins required to form the target sum is", result)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
class Solution {
/* Function to find the minimum number
of elements needed to form the target sum */
minimumCoins(coins, amount) {
const n = coins.length;
/* Create a 2D DP table with
n rows and amount+1 columns */
const dp = Array.from({ length: n }, () => Array(amount + 1).fill(0));
// Initialize the first row of the DP table
for (let i = 0; i <= amount; i++) {
if (i % coins[0] === 0)
dp[0][i] = Math.floor(i / coins[0]);
else
dp[0][i] = 1e9;
}
// Fill the DP table using a bottom-up approach
for (let ind = 1; ind < n; ind++) {
for (let target = 0; target <= amount; target++) {
/* Calculate the minimum elements needed
without taking the current element */
const notTake = dp[ind - 1][target];
/* Calculate the minimum elements
needed by taking the current element */
let take = 1e9;
if (coins[ind] <= target)
take = 1 + dp[ind][target - coins[ind]];
/* Store the minimum of 'notTake'
and 'take' in the DP table */
dp[ind][target] = Math.min(notTake, take);
}
}
// The answer is in the bottom-right cell
const ans = dp[n - 1][amount];
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= 1e9)
return -1;
// Return the minimum number of coins needed
return ans;
}
}
const coins = [1, 2, 3];
const amount = 7;
// Create an instance of Solution class
const sol = new Solution();
// Call the function to find the minimum coins
const result = sol.minimumCoins(coins, amount);
// Output the result
console.log("The minimum number of coins required to form the target sum is " + result);
Complexity Analysis:
Time Complexity:O(N*Target), as there are N*Target states therefore at max ‘N*Target’ new problems will be solved.Space Complexity:O(N*Target), as a 2D array of size N*Target is used.
If we observe the relation obtained in the tabulation approach, dp[ind][target] = dp[ind-1][target] + dp[ind-1][target-arr[ind]]. We see that to calculate a value of a cell of the dp array, only the previous row values (say prev) are need. So, we don’t need to store an entire array for that. Hence we can space optimize it.
Note: We first need to initialize the first row as we had done in the tabulation approach.
Steps to consider for space optimization:
- Declare two arrays to store results of subproblems 'prev' and 'cur'. Initialize the 'prev' array for the first element of the array, as we did in the tabulation approach, for handling the base case.
- Fill the 'cur' array using nested loops and the same logic discussed in tabulation. If the current element is less than or equal to the target, calculate 'take'.
- As, the problem is asking for minimum coins, store the minimum of 'take' and 'not take' in the 'cur' array.
- Update 'prev' with 'cur' for the next iteration and at last get the minimum number of coins needed for the target sum stored in 'prev[Target]'.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
#include <bits/stdc++.h>
using namespace std;
class Solution{
public:
/* Function to find the minimum number
of elements needed to form the target sum*/
int minimumCoins(vector<int>& coins, int amount) {
int n = coins.size();
/* Initialize two vectors to store
the previous and current DP states*/
vector<int> prev(amount + 1, 0);
vector<int> cur(amount + 1, 0);
// Initialize the first row of the DP table
for (int i = 0; i <= amount; i++) {
if (i % coins[0] == 0)
prev[i] = i / coins[0];
// Set it to a very large value if not possible
else
prev[i] = 1e9;
}
// Fill the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
for (int target = 0; target <= amount; target++) {
/* Calculate the minimum elements needed
without taking the current element*/
int notTake = prev[target];
/* Calculate the minimum elements
needed by taking the current element*/
int take = 1e9;
if (coins[ind] <= target)
take = 1 + cur[target - coins[ind]];
/* Store the minimum of 'notTake'
and 'take' in the current DP state*/
cur[target] = min(notTake, take);
}
/* Update the previous DP state with
the current state for the next iteration*/
prev = cur;
}
// The answer is in the last row of the DP table
int ans = prev[amount];
/* If 'ans' is still very large, it means
it's not possible to form the target sum*/
if (ans >= 1e9)
return -1;
// Return the minimum number of coins
return ans;
}
};
int main() {
vector<int> coins = {1, 2, 3};
int amount = 7;
//Create an instance of Solution class
Solution sol;
// Call the function to find the minimum coins
int result = sol.minimumCoins(coins, amount);
// Output the result
cout << "The minimum number of coins required to form the target sum is " << result << endl;
return 0;
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
import java.util.*;
class Solution {
/* Function to find the minimum number
of elements needed to form the target sum */
public int minimumCoins(int[] coins, int amount) {
int n = coins.length;
/* Initialize two arrays to store
the previous and current DP states */
int[] prev = new int[amount + 1];
int[] cur = new int[amount + 1];
// Initialize the first row of the DP table
for (int i = 0; i <= amount; i++) {
if (i % coins[0] == 0)
prev[i] = i / coins[0];
// Set it to a very large value if not possible
else
prev[i] = (int)1e9;
}
// Fill the DP table using a bottom-up approach
for (int ind = 1; ind < n; ind++) {
for (int target = 0; target <= amount; target++) {
/* Calculate the minimum elements needed
without taking the current element */
int notTake = prev[target];
/* Calculate the minimum elements
needed by taking the current element */
int take = (int)1e9;
if (coins[ind] <= target)
take = 1 + cur[target - coins[ind]];
/* Store the minimum of 'notTake'
and 'take' in the current DP state */
cur[target] = Math.min(notTake, take);
}
/* Update the previous DP state with
the current state for the next iteration */
System.arraycopy(cur, 0, prev, 0, amount + 1);
}
// The answer is in the last row of the DP table
int ans = prev[amount];
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= (int)1e9)
return -1;
// Return the minimum number of coins
return ans;
}
public static void main(String[] args) {
int[] coins = {1, 2, 3};
int amount = 7;
// Create an instance of Solution class
Solution sol = new Solution();
// Call the function to find the minimum coins
int result = sol.minimumCoins(coins, amount);
// Output the result
System.out.println("The minimum number of coins required to form the target sum is " + result);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
class Solution:
""" Function to find the minimum number
of elements needed to form the target sum """
def minimumCoins(self, coins, amount):
n = len(coins)
""" Initialize two lists to store
the previous and current DP states """
prev = [0] * (amount + 1)
cur = [0] * (amount + 1)
# Initialize the first row of the DP table
for i in range(amount + 1):
if i % coins[0] == 0:
prev[i] = i // coins[0]
# Set it to a very large value if not possible
else:
prev[i] = int(1e9)
# Fill the DP table using a bottom-up approach
for ind in range(1, n):
for target in range(amount + 1):
""" Calculate the minimum elements needed
without taking the current element """
notTake = prev[target]
""" Calculate the minimum elements
needed by taking the current element """
take = int(1e9)
if coins[ind] <= target:
take = 1 + cur[target - coins[ind]]
""" Store the minimum of 'notTake'
and 'take' in the current DP state """
cur[target] = min(notTake, take)
""" Update the previous DP state with
the current state for the next iteration """
prev[:] = cur
# The answer is in the last row of the DP table
ans = prev[amount]
""" If 'ans' is still very large, it means
it's not possible to form the target sum """
if ans >= int(1e9):
return -1
# Return the minimum number of coins
return ans
coins = [1, 2, 3]
amount = 7
# Create an instance of Solution class
sol = Solution()
# Call the function to find the minimum coins
result = sol.minimumCoins(coins, amount)
# Output the result
print("The minimum number of coins required to form the target sum is", result)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
class Solution {
/* Function to find the minimum number
of elements needed to form the target sum */
minimumCoins(coins, amount) {
let n = coins.length;
/* Initialize two arrays to store
the previous and current DP states */
let prev = new Array(amount + 1).fill(0);
let cur = new Array(amount + 1).fill(0);
// Initialize the first row of the DP table
for (let i = 0; i <= amount; i++) {
if (i % coins[0] === 0)
prev[i] = i / coins[0];
// Set it to a very large value if not possible
else
prev[i] = 1e9;
}
// Fill the DP table using a bottom-up approach
for (let ind = 1; ind < n; ind++) {
for (let target = 0; target <= amount; target++) {
/* Calculate the minimum elements needed
without taking the current element */
let notTake = prev[target];
/* Calculate the minimum elements
needed by taking the current element */
let take = 1e9;
if (coins[ind] <= target)
take = 1 + cur[target - coins[ind]];
/* Store the minimum of 'notTake'
and 'take' in the current DP state */
cur[target] = Math.min(notTake, take);
}
/* Update the previous DP state with
the current state for the next iteration */
prev = [...cur];
}
// The answer is in the last row of the DP table
let ans = prev[amount];
/* If 'ans' is still very large, it means
it's not possible to form the target sum */
if (ans >= 1e9)
return -1;
// Return the minimum number of coins
return ans;
}
}
const coins = [1, 2, 3];
const amount = 7;
// Create an instance of Solution class
const sol = new Solution();
// Call the function to find the minimum coins
const result = sol.minimumCoins(coins, amount);
// Output the result
console.log("The minimum number of coins required to form the target sum is " + result);
Complexity Analysis:
Time Complexity:O(N*Target), as there are N*Target states therefore at max ‘N*Target’ new problems will be solved.Space Complexity:O(Target), as a 2D array of size (Target+1) is used.
Frequently Occurring Doubts
Q: Why do we initialize dp[i] = ∞?
A: We start with an impossible state (∞) to ensure that min(dp[i], dp[i - coin] + 1) correctly selects the smallest number of coins.
Q: Why do we iterate over coins first instead of amount?
A: Iterating over coins first ensures that each amount is updated optimally, allowing each coin to contribute to smaller values before reaching larger ones.
Interview Followup Questions
Q: How would you modify the problem if you needed the total number of ways to make amount instead of the minimum coins?
A: Change dp[i] = min(dp[i], dp[i - coin] + 1) to summation: dp[i]+=dp[i−coin]
Q: Can this problem be solved efficiently using graph-based techniques?
A: Yes! Model the problem as a graph where each node is an amount and edges represent valid coin choices. A BFS (shortest path) approach finds the minimum steps.
Notes
Code
✅ Testcase
Input: {'coins': '[1, 2, 5]', 'amount': '11'}
Expected:
3
3
Actual: -
Time: -
sec
Status: Waiting
Input: {'coins': '[2, 5]', 'amount': '3'}
Expected:
-1
-1
Actual: -
Time: -
sec
Status: Waiting
Input: {'coins': '[1]', 'amount': '0'}
Expected:
0
0
Actual: -
Time: -
sec
Status: Waiting
Facts
- • This problem concept forms the foundation of many optimization algorithms in software development, especially in fields like logistics and inventory management
- • A practical example is in Change-Making Machines, common in supermarkets or large businesses
- • These machines are basically designed to solve this problem: provide change using the fewest number of coins
- • Another area is in resource or budget allocation in cloud computing and finance
- • Software tools, such as those used for project management, utilize this kind of algorithm to distribute resources efficiently