Count derangements
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).

Input format:

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.

Constraints:

1

Question

Count derangements

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).

Input format:

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.

Constraints:

1 <= T <= 100
1 <= N <= 3000

Time limit: 1 sec

Accepted Answer

Step 1 I followed the recursive approach initially, even though it passed all the cases.
Step 2 I still had time so changed it to DP, which reduced my time.

Accepted Answer

Recursive approach.

Let’s understand this approach with an example.

Consider ‘N’ = 4, the elements will be {0, 1, 2 ,3}.

The element 0 can be placed at any index except 0 because the element cannot be placed at the original position. So, the number of ways of placing 0 is 3, that is, at positions 1, 2, or 3.
To place element 1, we need to consider two situations:
1. 0 is placed at index 2 or 3 (index other than the index of current element). In this case, the number of ways in which element 1 can be placed is 2, that is, at positions 0 or {2,3} (because 0 will already be placed at position 2 or 3).
2. 0 is placed at position 1. In this case, 0 and 1 have swapped places and hence 1 is already deranged. So, we need not reconsider it.
For element 2, we again consider two conditions:
1. None among {0,1} have already swapped places with 2, that is, it is still at the original position. In this case, only 1 position is left for 2 to be placed as 2 elements {0,1} have already taken 2 positions and it cannot be placed at the original position.
2. One among {0,1} when deranged has swapped position with 2. So, no need to reconsider it.
If any other position is left for 3 other than index 3, the permutation generated is correct, else we discard it.

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 next element is still at its original position, so we send ‘n-1’ in recursion. This means now there are 'N' - 1 elements, 'N' - 1 positions and every element has 'N' - 2 choices.
The next element was already swapped by any previous element, we don’t reconsider it as it is already deranged, so we pass 'N' - 2 in recursion. This means now there are 'N' - 2 elements, 'N' - 2 positions and every element has 'N' - 3 choices.

The steps are as follows:

Take the base condition as:
1. If 'N' is equal to 1, return 0 because this means all the other elements have been deranged and only one element is left which could not find any other position and is still placed at its original place.
2. If 'N' is equal to 2, return 1.
Recur to find all possible permutations using

countDerangement('N')=('N' - 1) * [countDerangement('N' - 1)+countDerangement('N' - 2)].

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(2^n)Explanation:

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).

Accepted Answer

Bottom-up approach

We can observe that this implementation, recalculates various problems. So, to avoid this, the idea is to store the results of subproblems in an array and build the array in a bottom-up manner.

The steps are as follows:

Create an array ‘derangementCount’ of size ‘N’ to store the count of the derangements of subproblems.
Initialize the base cases, that is, ‘derangementCount[1]’ = 0 and 'derangementCount[2]' = 1.
Run a loop where ‘i’ ranges from 3 to ‘N’ and fill the array in bottom-up manner using ‘derangementCount[i]’ = ('i' - 1) * ('derangementCount['i' - 1]' + ‘derangementCount[i - 2]’).
Return 'derangementCount[N]', which stores the total number of derangements of ‘N’ elements.

Space Complexity: O(n)Explanation:

O(N), Where 'N' is the number of elements.

Since an array of length 'N' is used. Thus the space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where 'N' is the number of elements.

Since an array of length 'N' is filled. Thus the time complexity will be O(N).

Accepted Answer

Optimised approach

The steps are as follows:

In the bottom-up approach, extra space is used to store subproblems. However, we only need two previous values to calculate the count of derangements of the current value of ‘N’.
Instead of storing in an array, two variables are used to store the two previous values.
Initialize two variables, ‘prevOne’ and ‘prevTwo’ to 0 and 1 respectively.
Run a loop where ‘i’ ranges from 3 to ‘N’.
Find the count of derangements for the current value of ‘i’ using ‘CUR’ = ('i' - 1) * ('prevOne' + ‘prevTwo’).
Store the value of ‘prevOne’ in ‘prevTwo’ and the value of ‘CUR’ in ‘prevOne’.
Return ‘prevTwo’ which stores the total number of derangements of ‘N’ elements.

Space Complexity: O(1)Explanation:

O(1)

Since it uses constant space. Thus the space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of elements.

Since a loop of range ‘N’ was run to find the possible number of derangements of ‘N’ elements. Thus the time complexity will be O(N).

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:

Input format:

Output Format:

Note:

Constraints:

Top Nagarro Technical Trainee interview questions & answers

Popular interview questions of Technical Trainee