634. Find the Derangement of An Array π
Description
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
You are given an integer n
. There is originally an array consisting of n
integers from 1
to n
in ascending order, return the number of derangements it can generate. Since the answer may be huge, return it modulo 109 + 7
.
Example 1:
Input: n = 3 Output: 2 Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
Example 2:
Input: n = 2 Output: 1
Constraints:
1 <= n <= 106
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ as the number of derangement of an array of length $i$. Initially, $f[0] = 1$, $f[1] = 0$. The answer is $f[n]$.
For an array of length $i$, we consider where to place the number $1$. Suppose it is placed in the $j$-th position, where there are $i-1$ choices. Then, the number $j$ has two choices:
- Placed in the first position, then the remaining $i - 2$ positions have $f[i - 2]$ derangements, so there are a total of $(i - 1) \times f[i - 2]$ derangements;
- Not placed in the first position, which is equivalent to the derangement of an array of length $i - 1$, so there are a total of $(i - 1) \times f[i - 1]$ derangements.
In summary, we have the following state transition equation:
$$ f[i] = (i - 1) \times (f[i - 1] + f[i - 2]) $$
The final answer is $f[n]$. Note the modulo operation in the answer.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 |
|
Solution 2: Dynamic Programming (Space Optimization)
We notice that the state transition equation only relates to $f[i - 1]$ and $f[i - 2]$. Therefore, we can use two variables $a$ and $b$ to represent $f[i - 1]$ and $f[i - 2]$ respectively, thereby reducing the space complexity to $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 |
|