'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',
Update appNew update is available. Click here to update.
Last Updated: 31 Dec, 2020

Number of Ways

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

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

Approaches

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