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
}

All Problems

All Solutions