Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Coin Change(Finite Supply)

Hard
0/120
profile
Contributed by
8 upvotes
Asked in companies
AmazonAdobeMicrosoft

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 )
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
Full screen
Console