Ninja's Classroom

Moderate
0/80
5 upvotes
Asked in companies
Adobe314e Corporation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
3
Sample Output 1:
3
5
Explanation of sample input 1:
For the first test case,
The number of distinct possible arrangements is 3. They are ‘00’,’10’, ‘01’.
 where 1 represents an angry student and 0 represents a normal student.
 Hence the answer is 3.

For the second test case:
The number of distinct possible arrangements is 5. 
They are ‘000’,’101’, ‘001’,’100’ and ‘010’.
 where 1 represents an angry student and 0 represents a normal student.
 Hence the answer is 4.
Sample Input 2:
2
1
5
Sample Output 2:
2
13
Hint

Check for all possible combinations.

Approaches (3)
Using Recursion.

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

O(2^N), where ‘N’ is the number of seats in the classroom.

 

In this approach, we are checking for all possible arrangements and there are 2 choices for each seat. So the total number of combinations is 2^N. Hence the overall time complexity is O(2^N).

Space Complexity

O(2^N), where ‘N’ is the number of seats in the classroom.

 

In this approach, in the worst case, there will be 2^N recursive calls of function HELPER(). So the stack memory used is of the order 2^N. Hence the space complexity is O(2^N).

Code Solution
(100% EXP penalty)
Ninja's Classroom
Full screen
Console