Number of Ways

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
5 upvotes
Asked in companies
AppleSnapdeal

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
8

Sample Output 1:

1

Explanation of Sample Input 1:

{3,5} and {5,3} are two possible permutations but these represent the same combination. Thus, the output is 1.

Sample Input 2:

2
20
13

Sample Output 2:

4
2

Explanation of sample output 2:

For test case 1 :  N  = 20
Possible distinct combinations are :
3 3 3 3 3 5
5 5 5 5 
5 5 10 
10 10 

For test case 2 : N = 13
Possible distinct combinations are :
3 5 5 
3 10
Hint

Think of trying all possible combinations.

Approaches (3)
Brute Force Approach

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

O(2^N) where ‘N’ is the total amount.

 

Using every coin we are finding the count of distinct combinations for almost all the values from 0 to ‘N’. This takes exponential time, that is ‘2 ^ N’. Thus, the total time complexity is O(2 ^ N). 

Space Complexity

O(N), where ‘N’ is the total amount.

 

We are using recursion. So O(N) space will be taken by the recursion stack. Thus the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Number of Ways
Full screen
Console