Last Updated: 24 Feb, 2021
Count Derangements
Moderate
Asked in companies
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.
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
Approaches
- There are (N – 1) ways for element 0. Hence the, we will multiply by N - 1 for every state.
- 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.
- Therefore, the final ans would be (N - 1) * (derangements[N - 1] + derangements[N - 2]).
We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need to solve the same subproblems repeatedly.
Here is the algorithm:
- There are (N – 1) ways for element 0. Hence, we will multiply by N - 1 for every state.
- 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.
- Therefore, the final ans would be (N - 1) * (derangements[N - 1] + derangements[N - 2]).
- If we need to find the value for some state N, instead of starting from the base state, we see if our answer has been processed before and use it, this is called memoization.
- Store each state in an array so that recurring states are not calculated every time.
We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need to solve the same subproblems repeatedly.
Here is the algorithm:
- The answer is for ( N-1 * dp[N-1] + dp[N-2] ), where the DP array stores the solution for every N state, and N is the number given.
- We only need to remember only two previous values.
- So, instead of Storing the values in an array, two variables can be used to store the required previous only.
- Just iterate from 0 to N and store two states in 2 variables.
- For the final N, the answer would be the last stored state.
Similar problems