Count Derangements

Moderate
0/80
Average time to solve is 25m
10 upvotes
Asked in companies
MicrosoftMAQ SoftwareLTI - Larsen & Toubro Infotech

Problem statement

Given a number ‘N', the task is to find the total number of derangements of a set of ‘N’ elements.

A ‘Derangement’ is a permutation of 'N' elements, such that no element appears in its original position. For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.

For example, 'N' = 2 , {0, 1} and {1, 0} are the only derangement therefore output will be 1.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains an integer 'N', the size of the permutation.

Output format :

For each test case, print the total number of derangements of a set of n elements.

The output of each test case will be printed in a separate line.

Note:

The ‘answer’ could be very large, thus output ‘answer’ % (10 ^ 9 + 7).
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5*10^3

Time Limit: 1 sec

Sample Input 1 :

2
2
1

Sample Output 1 :

1
0

Explanation For Sample Input 1:

For the first test case, For two elements say {0, 1}, there is only one possible derangement {1, 0}.

For the second test case, For one element say {0}, it is not possible to any derangement because there is only one element and it is always placed in its original position.

Sample Input 2 :

2
4
3

Sample Output 2 :

9
2
Hint

Can you form the recurrence relation? 

Approaches (3)
Recursion
  1. There are (N – 1) ways for element 0. Hence the, we will multiply by N - 1 for every state.
  2. Let 0 be placed at index i. Now, there are there two possibilities, depending on whether or not element i is set at 0 :
    • i is placed at 0: This case is equivalent to solving the problem for (N - 2) elements as two elements have just swapped their positions.
    • i is not placed at 0: This case is equivalent to solving the problem for( N - 1) elements as now there are (N - 1) elements, (N - 1) positions, and every element has (N - 2) choices.
  3. Therefore, the final ans would be (N - 1) * (derangements[N - 1] + derangements[N - 2]).
Time Complexity

O(2 ^ N), where N is the number given.

 

This is because for every state we have two options. Thus, the final time complexity will be O(2 ^ N).

Space Complexity

O(N), where N is the number given.

 

Since we are using recursion, and at the moment recursion stack here can have N items. Thus, the final space complexity will be O(N).

Code Solution
(100% EXP penalty)
Count Derangements
Full screen
Console