Ninja And His Exam

Easy
0/40
Average time to solve is 15m
6 upvotes
Asked in company
Ola

Problem statement

Ninja has an exam tomorrow. He has not studied well for it. So, he decided to get only the passing marks. Ninja knows that the exam will consist of three types of questions, having marks 2, 5 and 7 respectively. He needs to find the number of ways he can achieve passing marks in the exam by attempting those questions. He asked you to help him with this as he is busy preparing. So, you need to find out the number of ways he can score the passing marks.

Example : 
Let us suppose the passing marks is: 10
So, the number of ways Ninja can score 10 marks are (2, 2, 2, 2, 2) and (5, 5), so you need to print 2.
Note : 
Keep in mind that a particular test has infinite questions of each type.
Keep in mind that the ninja does not want more than the passing marks.
Please note that (2, 5) and (5, 2) are the same and you need to take them as a single way.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ denoting the passing marks of the test.
Output Format : 
For each test case, print a single integer that denotes the number of ways to reach the given marks.

Output for every test case will be printed in a separate line.
Constraints : 
1 <= T <= 50
0 <= N <= 10000

Time limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1 :
2
10
20
Sample Output 1 :
2
5
Explanation of sample input 1 :
In the first test case, 
The number of ways Ninja can score 10 marks are:(2, 2, 2, 2, 2) and (5, 5), so you need to print 2.

In the second test case, 
The number of ways Ninja can score 20 marks are: (2, 2, 2, 2, 2, 2, 2, 2, 2, 2), (2, 2, 2, 7, 7), (2, 2, 2, 2, 2, 5, 5), (2, 2, 2, 2, 5, 7) and (5, 5, 5, 5) so you need to print 5.
Sample Input 2 :
3
8
13
9
Sample Output 2 :
1
2
2
Explanation of sample input 2 :
In the first test case, 
The number of ways Ninja can score 8 marks is :(2, 2, 2, 2), so you need to print 1.

In the second test case, 
The number of ways Ninja can score 13 marks are:(2, 2, 2, 7) and (2, 2, 2, 2, 5), so you need to print 2.

In the third test case, 
The number of ways Ninja can score 9 marks are:(2, 7) and (2, 2, 5), so you need to print 2.
Hint

Can you break your problem into smaller repetitive sub problems?

Approaches (3)
Recursion

The simplest idea to solve this problem is to use recursion. For every question, Ninja has two choices, either he will attempt it at least once or not. So we will make a recursive function and count all the ways to get given marks by attempting either 2, 5, or 7 mark questions.

 

Algorithm:

  • Store the marks of the questions in an array ‘m’ such that m = [2, 5, 7].
  • Let reachScore (m, idx, N) be our recursive function where ‘idx’ is the index to the last element of array ‘m’ and ‘N’ is passing marks.
  • Return reachScore (m, idx, N -m[idx] ) + reachScore (m, idx-1, N )
  • Base Cases:
    • If N = 0, it means we found a way to reach the given score. So return 1.
    • If N < 0., then there can be no way to reach the given score.So return 0.
    • If N>0 and idx < 0 return 0;
Time Complexity

O(2 ^ N), where ‘N’ is the integer given, i.e passing marks.

 

The maximum distance of the parent node to a leaf node in the recursion tree will be ‘N’. So, the overall time complexity is O(2 ^ N).

Space Complexity

O(1)

 

No extra space is required, so the space complexity is 

O(1).

Code Solution
(100% EXP penalty)
Ninja And His Exam
Full screen
Console