Problem of the day
A Derangement is a permutation of ‘N’ elements, such that no element appears in its original position. For example, an instance of derangement of {0, 1, 2, 3} is {2, 3, 1, 0}, because 2 present at index 0 is not at its initial position which is 2 and similarly for other elements of the sequence.
Given a number ‘N’, find the total number of derangements possible of a set of 'N’ elements.
Note:The answer could be very large, output answer %(10 ^ 9 + 7).
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line and the only line of each test case contains an integer ‘N’ denoting the number of elements whose derangements are to be counted.
Output Format:
For each test case, return the total number of derangements of a set of ‘N’ elements.
Note:
You don't need to print anything, it has been already taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 3000
Time limit: 1 sec
2
2
3
1
2
In test case 1, For two elements say {0, 1}, there is only one possible derangement {1, 0}. 1 is present at index 0 and not at its actual position, that is, 1. Similarly, 0 is present at index 1 and not at its actual position, that is, 0.
In test case 2, For three elements say {0, 1, 2}, there are two possible derangements {2, 0, 1} and {1, 2, 0}. In both the derangements, no element is present at its actual position.
2
1
4
0
9
In test case 1, For the array = {0}, there is no possible derrangements. Hence the answer is 0 (zero).
In test case 2, For the array elements = {0, 1, 2, 3}, total 9 derrangements are possible. One of them is: { 3, 2, 1, 0}.
Think about how the position for each element will be assigned.
Let’s understand this approach with an example.
Consider ‘N’ = 4, the elements will be {0, 1, 2 ,3}.
Below is the recursive relation for it.
countDerangement(n) = ('N' - 1) * [countDerangement('N' - 1) + countDerangement('N' - 2)]
How does the above recursive relation work?
An element can be placed at any index other than its original index and the indexes where previous elements are placed, that means, there are 'N' - 1 possible positions, which explains multiplication by ('N' - 1).
There are two possibilities:
The steps are as follows:
countDerangement('N')=('N' - 1) * [countDerangement('N' - 1)+countDerangement('N' - 2)].
O(2 ^ N), Where 'N' is the number of elements.
Since all possible permutations are found such that no element appears in its original position. Thus the time complexity is O(2 ^ N).
O(N), Where 'N' is the number of elements.
Since recursive stack uses space of the order 'N'. Thus the space complexity will be O(N).