Number of Ways

Posted: 31 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Consider a game in which players can choose any of the three coins => 3 or 5 or 10 in a move. There is an infinite supply of all the three types of coins. Given a total amount ‘N’, find the distinct combinations which sums up to 'N'.

Note :
3,5 and 5,3 are not distinct combinations.

Input format:

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. 

Output format:

For each test case, return the number of distinct combinations to reach the total amount is printed.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 5 * 10^4

Time Limit: 1 sec
Approach 1

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.
Try Problem