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 <= 106We 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:
i - 2 positions have f[i - 2] derangements, so there are a total of (i - 1) times f[i - 2] derangements;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)$.
Java
C++
Go
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).
Java
C++
Go
| Approach | Complexity |
|---|---|
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,117 views views
Watch 9 more video solutions →Practice Find the Derangement of An Array with our built-in code editor and test cases.
Practice on FleetCode