Last Updated: 10 Sep, 2021
Ninja's Classroom
Moderate
Asked in companies
The students of Ninjaland are going through tough practice, so some of them are a little irritated and angry. So, In a classroom, if two sad angry students sit adjacent to each other, they are likely to fight.
There are ‘N’ seats in the classroom. How many distinct arrangements of students can sit in these ‘N’ seats such that no students are likely to fight. As the number of such arrangements can be very large.Return answer % (10^9 +7).
For Example
For the given if N = ‘3’, the possible number of arrangements is 5.
They are ‘000’,’101’, ‘001’,’100’ and ‘010’. Here 1 represents an Angry student and 0 represents a normal student.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N’ denoting the number of seats in the class.
Output Format:
For each test case, print an integer corresponding to the number of distinct possible arrangements % (10^9 +7).
Print the output of each test case in a separate line.
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 <= 5000.
Time limit: 1 sec
Approaches
In this approach, we will declare a recursive function HELPER(‘CUR’, ’LAST’) that will return the number of arrangements with ‘CUR’ seats and the last student as ‘LAST’. The base case will be if CUR == 1, return 1.
If LAST is equal to 1, we can only add a 0, so return HELPER(‘CUR’-1,0).
If LAST is equal to 0,we can add both 1 and 0 ,so return ( HELPER(‘CUR’-1,1) + HELPER(‘CUR’-1,0) ) % (10^9 + 7).
Our final answer will be ( HELPER(‘N’,0) + HELPER(‘N’,1) ) %(10^9 + 7).
Algorithm:
- Defining function HELPER(‘CUR’, ’LAST’).
- If ‘CUR’ is equal to 1, return 1. (Base Case.)
- If ‘LAST’ is equal to 0:
- Return ( HELPER(‘CUR’-1, 1) + HELPER(‘CUR’-1, 0) ) % (10^9 +7).
- If ‘LAST’ is equal to 1:
- Return HELPER(‘CUR’ - 1,0).
- Declare ‘ANS’ to store the final answer.
- Set ‘ANS’ as ( HELPER(‘N’, 1) + HELPER(‘N’, 0) )% (10^9 +7).
- Return ‘ANS’.
As in the approach-1, we have used a recursive function to find the answer. In this approach, we will use the same function but we will store the answer returned by the function in a DP array. So that if the answer is already computed, we can use that answer and reduce the time complexity efficiently.
Algorithm:
- Defining function HELPER(‘CUR’, ’LAST’, ’DP’).
- If ‘CUR’ is equal to 1, return 1. (Base Case.)
- If DP[‘CUR’][‘LAST’] is not equal to -1, do the following:
- Value for this state is already computed, so return that value.
- Return DP[‘CUR’][‘LAST’].
- If ‘LAST’ is equal to 0:
- Set DP[‘CUR’][‘LAST’] as ( HELPER(‘CUR’-1, 1, ‘DP’) + HELPER(‘CUR’-1, 0, ‘DP’) ) % (10^9 +7).
- If ‘LAST’ is equal to 1:
- Set DP[‘CUR’][‘LAST’] as HELPER(‘CUR’ - 1,0, ‘DP’).
- Return DP[ ‘CUR’ ][ ‘LAST’ ].
- Declare ‘ANS’ to store the final answer.
- Declare a ‘DP’ array of size [N+1][2] to memoize this solution.
- Set all values of ‘DP’ as -1.
- Set ‘ANS’ as (HELPER(‘N’, 1, ‘DP’) + HELPER(‘N’, 0, ‘DP’))% (10^9 +7).
- Return ‘ANS’.
In this approach, we will declare two arrays ‘LASTONE’ and ‘LASTZERO’. LASTONE[i] stores the number of arrangements possible that ends with ‘1’. Similarly, LASTZERO[i] will store the number of arrangements possible that ends with ‘0’. We will fill these as
- LASTONE[i] = LASTZERO[i-1] as ‘1’ can be added at the end only if the end is zero.
- LASTZERO[i] = ( ‘LASTZERO’[i-1] + ‘LASTONE’[i-1]) % (10^9 +7).
We will return the final answer as (‘LASTONE’[‘N’] + ‘LASTZERO’[‘N’]) % (10^9 +7).
Algorithm:
- Declare two arrays ‘LASTONE’ and ‘LASTZERO’ of size ‘N’ + 1.
- Set ‘LASTONE’[1] as 1.
- Set ‘LASTZERO’[1] as 1.
- For each index i in range 2 to N,do the following:
- Set ‘LASTONE’[i] as ‘LASTZERO’[i-1].
- Set ‘LASTZERO’[i] as ( ‘LASTZERO’[i-1] + ‘LASTONE’[i-1]) % (10^9 +7).
- Set ‘ANS’ as (‘LASTZERO’[N] + ‘LASTONE’[N]) % (10^9 +7).
- Return ‘ANS’.
Similar problems