Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/634.html
634. Find the Derangement of An Array
Level
Medium
Description
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
There’s originally an array consisting of n
integers from 1 to n
in ascending order, you need to find the number of derangement it can generate.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
Input: 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
Note:
n
is in the range of [1, 106].
Solution
Let f(n) be the number of derangement that can be generated using n integers. Obviously, f(1) = 0 and f(2) = 1. For n > 2, how to calculate f(n)?
Use dynamic programming, where f(n) can be obtained using f(n - 1) and f(n - 2). If there are n numbers, then the greatest number n can be placed in any position from 1 to n - 1. Suppose number n is placed in position m where 1 <= m < n, then number m must be in a position that is not its original position. If number m is in position n, then the situation becomes a derangement of n - 2 remaining numbers, so the number of derangement is f(n - 2). If number m is not in position n, then for each number from 1 to n - 1, there is exactly one position that the number can’t be in. For number m, the one position it can’t be in is position n. For other numbers like number k where k != m and k < n, the one position it can’t be in is position k. So the number of derangement is f(n - 1). In conclusion, if there are n numbers and number n is placed in position m where 1 <= m < n, then the number of derangement is f(n - 2) + f(n - 1). Since there are n - 1 possible values for m, the number of derangement in total is f(n) = (f(n - 2) + f(n - 1)) * (n - 1).
For each m such that 1 <= m <= n, after f(m) is calculated, do the modulo operation. Finally, return f(n).
-
class Solution { public int findDerangement(int n) { if (n <= 3) return n - 1; final int MODULO = 1000000007; long[] dp = new long[n]; dp[0] = 0; dp[1] = 1; for (int i = 2; i < n; i++) dp[i] = (dp[i - 2] + dp[i - 1]) * i % MODULO; return (int) dp[n - 1]; } }
-
class Solution { public: int findDerangement(int n) { long long a = 1, b = 0; const int mod = 1e9 + 7; for (int i = 2; i <= n; ++i) { long long c = (i - 1) * (a + b) % mod; a = b; b = c; } return b; } };
-
class Solution: def findDerangement(self, n: int) -> int: mod = 10**9 + 7 a, b = 1, 0 for i in range(2, n + 1): a, b = b, ((i - 1) * (a + b)) % mod return b
-
func findDerangement(n int) int { a, b := 1, 0 const mod = 1e9 + 7 for i := 2; i <= n; i++ { a, b = b, (i-1)*(a+b)%mod } return b }