Coin Change(Finite Supply)

Hard
0/120
profile
Contributed by
15 upvotes
Asked in companies
IBMAdobeAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1 2 4
1 1 1
7
3
1 2 4
2 3 2
7
Sample Output 1 :
1
2
Explanation For Sample Input 1 :
In the first test case, there is only one possible way to make the sum equal to 7 i.e., taking all the coins. Hence answer is 1.

In the second test case, You can make the sum seven by using the following coins:
{1, 2, 4}, {1, 2, 2, 2}. Hence the answer is 2.
Sample Input 2 :
2
4
1 11 7 6
1 2 3 1
10
3
5 1 2
1 1 3
6
Sample Output 2 :
0
2
Hint

Recursively call all the possible changes and check if the sum is equal to the required sum.

Approaches (3)
Recursion Approach

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’.
Time Complexity

O( 2 ^ sumFreq ), where ‘sumFreq’ is the sum of all the coins of each denomination.

 

As we are going through all possible coin combinations and the total number of coins is ‘sumFreq’. Thus, either we can select them or we will not use them.

Hence the time complexity is O( 2 ^ sumFreq ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Coin Change(Finite Supply)
Full screen
Console