Last Updated: 28 Feb, 2021
Ninja And His Exam
Easy
Asked in company
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.
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.
Approaches
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;
In the recursive approach, some subproblems are overlapped making them to be solved more than one time. This problem can be solved by using memoization.
The recursive approach can be optimized by maintaining an extra 2-d array “res” that stores the result of the recursive calls. For every sub-problem, we first check the “res” array. If the value is already computed we simply return it otherwise we calculate it using recursion and put it in the “res” array.
Algorithm:
- Initialize a 2-D array “res” of ‘ N+1’ rows and ‘3’ columns and initialize its values to -1.
- For i : 0 to 2, res[0][ i ] = 1.
- Let reachScore (m, idx, N) be our recursive function.
- res[ N ][ idx ] = reachScore (m, idx, N -m[idx] ) + reachScore (m, idx-1, N ).
- Return res[ N ][ idx ] .
- Base Case
- If ‘N’ = 0 and “idx” > =0
- return res[ N ][ idx ]=1.;
- If ‘N’ < 0 or “idx” < 0
- i. return 0.
- If ‘N’ = 0 and “idx” > =0
The basic approach used to solve this problem is to use a DP array of size ‘N + 1’, that will store the count of all marks from 0 to N, and for every possible question solved we will simply increment the values in the created array.
Algorithm:
- Create a DP array to store the count of solutions for a given mark.
- Initialise all values of DP as 0.
- Create a base case for DP. In this case:
- DP[0] = 1, if the given value is 0
- Now start considering the given marks(2, 5, 7) and update the DP values after the index greater than or equal to the value of the given mark.
- Finally, return the value stored in the DP at index = N, which means the count of ways of choosing questions with total marks equal to the passing marks ‘N’.