'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity', 'Knowing how to code is a major requirement for
astronomers', 'The first computer didn’t use any electricity', 'Do you
know there is a coding language named “Go“', 'Computer programming is one
of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the
name of the first programming language', 'The first programmer was the
daughter of a mad poet', 'Many programming languages share the same
structure', 'Coding will soon be as important as reading', 'How many
programmers does it take to change a light bulb? None, that’s a hardware
problem', 'Why do Java developers wear glasses? Because they can’t C',
'Software and temples are much the same — first we build them, then we
pray', 'An engineer will not call it a bug — it’s an undocumented
feature', 'In a room full of top software designers, if two agree on the
same thing, that’s a majority', 'C programmers never die. They are just
cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java',
'The best thing about a boolean is even if you are wrong, you are only off
by a bit', 'Linux is only free if your time has no value', 'The computer
was born to solve problems that did not exist before', 'Coding has over
700 languages', '67% of programming jobs aren’t in the technology
industry', 'Coding is behind almost everything that is powered by
electricity', 'Knowing how to code is a major requirement for
astronomers', 'The first computer didn’t use any electricity', 'Do you
know there is a coding language named “Go“', 'Computer programming is one
of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the
name of the first programming language', 'The first programmer was the
daughter of a mad poet', 'Many programming languages share the same
structure', 'Coding will soon be as important as reading', 'How many
programmers does it take to change a light bulb? None, that’s a hardware
problem', 'Why do Java developers wear glasses? Because they can’t C',
'Software and temples are much the same — first we build them, then we
pray', 'An engineer will not call it a bug — it’s an undocumented
feature', 'In a room full of top software designers, if two agree on the
same thing, that’s a majority', 'C programmers never die. They are just
cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java',
'The best thing about a boolean is even if you are wrong, you are only off
by a bit', 'Linux is only free if your time has no value', 'The computer
was born to solve problems that did not exist before',

Problem of the day

New update is available. Click here to update.

Last Updated: 31 Dec, 2020

Moderate

```
3,5 and 5,3 are not distinct combinations.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and only line of each test case contains an integer ‘N’ , the total amount.
```

```
For each test case, return the number of distinct combinations to reach the total amount is printed.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 5 * 10^4
Time Limit: 1 sec
```

To count all possible distinct combinations to reach the total amount of ‘N’ using coins of 3,5 and 10, we can divide all solutions in two sets.

- Solutions that contain the ith type of coin.
- Solutions that do not contain the ith type of coin.

The total number of distinct combinations can be found using recursion.

Algorithm:

- Recursive Function: 'COUNT_WAYS_HELPER'(coins, M, N), where ‘coins’ is the list of coins available, that is {3,5,10}, ‘M’ is the type of coin available (one out of 3, 5 and 10) and ‘N’ is the total amount.
- Base conditions =>
- If ‘N’ becomes 0, return 1.
- If ‘N’ becomes negative, return 0.
- If ‘M’ becomes negative, return 0.

- There will be two cases :
- Find all combinations which include Mth type of coin in it and sums up to the total amount : countWaysHepler(coins, m, N-coins[m]).
- Find all combinations which does not include Mth type of coin in it and sums up to the total amount : 'COUNT_WAYS_HELPER'(coins, m-1, N)
- Return the sum of above two cases.

The idea is the same as the previous approach, but in the previous approach, many recursive calls were made again and again with the same parameters.

In the below diagram, the two parameters are : (coins array, total amount).

It is very clear that there are overlapping subproblems. This can be eliminated by storing the value obtained from a particular call in a 2d array, called the 'TABLE_ARRAY'.

'MEMO'[i][j] stores the count of distinct combinations which sums up to ‘i’ and once includes the jth coin and once excluding the ith coin.

Algorithm:

- Create a 'MEMO' array of size [N+1][3] and initialize all its values with -1.
- Recursive Function: 'COUNT_WAYS_HELPER'(COINS, M, N), where ‘COINS' is the list of coins available, that is {3,5,10}, ‘M’ is the type of coin available (one out of 3, 5, and 10) and ‘N’ is the total amount.
- Base conditions =>
- If ‘N’ becomes 0, return 1.
- If ‘N’ becomes negative, return 0.
- If ‘M’ becomes negative, return 0.
- If, 'MEMO'[N][M] is not -1, return its value.

- There will be two cases :
- Find all combinations which include M'th type of coin in it and sums up the total amount: countWaysHepler('COINS', m, N-coins[m]).
- Find all combinations which do not include Mth type of coin in it and sum up to the total amount: 'COUNT_WAYS_HELPER'(COINS, M-1, N)
- Update the sum of the above two cases in 'MEMO'[N][M] and return its value.
- Return the value of 'MEMO'[N][2].

For every type of coin, go through all the amounts ‘j’ , such that 0 <= j <= N, and update the value of 'DP'[j] as 'DP'[j] = 'DP'[j] + 'DP'[j - value of current coin]. This will add the count of distinct combinations that sums up to ‘j’ and that includes the current type of coin. And 'DP'[j] already had some value which was the count of distinct combinations that sums up to ‘j’, but only includes the coin that has occurred before the current coin in the coins array. Thus, at this point, 'DP'[j] contains the count of distinct combinations that sums up to ‘j’ with and without including all the coins up to the current type of coin.

Algorithm:

- Take a 'DP' array of size ‘N+1’ and initialize all its values with 0.
- 'DP'[0] = 1
- For every type of coin :
- Iterate over the 'DP' array for all ‘j’ (such that : value of current coin <= j <= N), 'DP'[j] = 'DP'[j] + 'DP'[j - value of current coin].
- Return the value of 'DP'[N] that is the count of distinct combinations that sums up to ‘N’.