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

Problem of the day

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.

```
‘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

```
1 <= T <= 10
1 <= N <= 100
1 <= coins[i] <= 100
1 <= freq[i] <= 100
1 <= V <= 100
Time limit: 1 sec
```

```
2
3
1 2 4
1 1 1
7
3
1 2 4
2 3 2
7
```

```
1
2
```

```
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.
```

```
2
4
1 11 7 6
1 2 3 1
10
3
5 1 2
1 1 3
6
```

```
0
2
```