Last Updated: 12 Oct, 2021
Coin Change(Finite Supply)
Hard
Asked in companies
You are given an array of integers ‘coins’ denoting the denomination of coins and another array of integers ‘freq’ denoting the number of coins of each denomination.
You have to find the number of ways to make the sum ‘V’ by selecting some(or all) coins from the array.
The answer can be very large. So, return the answer modulo 1000000007.
For Example :
‘N’ = 3, ‘coins’ = {1, 2, 3}, ‘freq’ = {1, 1, 3}, ‘V’ = 6
For the given example, we can make six by using the following coins:
{1, 2, 3}
{3. 3}
Hence, the answer is 2.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the total number of coins.
The second line of the test case contains ‘N’ integers denoting the elements of the array ‘coins’.
The third line of the test case contains ‘N’ integers denoting the elements of the array ‘freq’.
The fourth line of the test case contains the integer ‘V’ denoting the change we want.
Output Format :
For each test case, print a single integer denoting the total number of possible ways to get change ‘V’.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 100
1 <= coins[i] <= 100
1 <= freq[i] <= 100
1 <= V <= 100
Time limit: 1 sec
Approaches
In this approach, we will check whether we can make the required change for the current selected coin or we have to go to the next coin. So, basically we will check all the possible combinations which can be made from the given coins.
The steps are as follows:
- Return the function ‘coinChangeHelper’ and pass the vectors ‘coins’, ‘frequency’, the final change required, frequency of the last element as ‘supply’ and ‘N - 1’ as ‘index’.
‘coinChangeHelper(coins, freq, V, supply, index)’:
- In this function, check if either ‘V’ < 0 or supply < 0 or index < 0:
- Return 0.
- Check if the value of ‘V’ is equal to 0.
- If the value of ‘V’ is 0, return 1.
- Take an integer ‘answer’ and initialize it with 0.
- Check if supply is greater than 0 and ‘V’ - coins[index] >= 0:
- Update answer = ‘coinChangeHelper(coins, freq, v - coins[index], supply - 1, index)’
- Update ‘answer’ += ‘coinChangeHelper(coins, freq, v, freq[index - 1], index)’ % 1000000007.
- Return ‘answer’.
In this approach, we will check whether we can make the required change for the current selected coin or we have to go to the next coin but to reduce the time complexity we will use a dp array to store all the values we have calculated.
The steps are as follows:
- Take a 3D array ‘dp’ to store the number of possible ways to make the change ‘V’ and initialize it with -1.
- Return the function ‘coinChangeHelper’ and pass the vectors ‘coins’, ‘frequency’, the final change required, frequency of the last element as ‘supply’, ‘N - 1’ as ‘index’, and the ‘dp’ array.
‘coinChangeHelper(coins, freq, V, supply, index, dp)’:
- In this function, check if either ‘V’ < 0 or supply < 0 or index < 0:
- Return 0.
- Check if the value of ‘V’ is equal to 0.
- If the value of ‘V’ is 0, return 1.
- Check if the value of dp[index][v][supply] is not equal to -1:
- Return dp[index][v][supply].
- Take an integer ‘answer’ and initialize it with 0.
- Check if supply is greater than 0 and ‘V’ - coins[index] >= 0:
- Update answer = ‘coinChangeHelper(coins, freq, v - coins[index], supply - 1, index)’
- Update ‘answer’ += ‘coinChangeHelper(coins, freq, v, freq[index - 1], index)’ % 1000000007.
- Update the value of ‘dp[index][v][supply]’ = ‘answer’.
- Return ‘answer’.
In this approach, we will iterate through the arrays ‘coins’ and ‘freq’, and for each coin, we will calculate the total ways to make all the coins from 1 to ‘V’ and update the dp array.
The steps are as follows:
- Take a 3D array ‘dp’ to store the number of possible ways to make the change ‘v’ and initialize it with 0.
- Iterate through the loop from 0 to n - 1(say iterator be i):
- Iterate through the loop from 0 to freq[i](say iterator be j):
- Update dp[0][i][j] = 1.
- Iterate through the loop from 0 to freq[i](say iterator be j):
- Iterate through the loop from 1 to v(say iterator be i):
- Iterate through the loop from 0 to n-1(say iterator be j):
- Iterate through the loop from 0 to ‘freq[j]’(say iterator be k):
- Update dp[i][j][k] = (dp[i - coins[j]][j][k - 1] + dp[i][j - 1][freq[i - 1]]) % 1000000007.
- Iterate through the loop from 0 to ‘freq[j]’(say iterator be k):
- Iterate through the loop from 0 to n-1(say iterator be j):
- Return dp[v][n - 1][freq[n - 1]].