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)\).

Python3JavaC++Go

class Solution:
    def findDerangement(self, n: int) -> int:
        mod = 10**9 + 7
        f = [1] + [0] * n
        for i in range(2, n + 1):
            f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod
        return f[n]

class Solution {
    public int findDerangement(int n) {
        long[] f = new long[n + 1];
        f[0] = 1;
        final int mod = (int) 1e9 + 7;
        for (int i = 2; i <= n; ++i) {
            f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % mod;
        }
        return (int) f[n];
    }
}

class Solution {
public:
    int findDerangement(int n) {
        long long f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        const int mod = 1e9 + 7;
        for (int i = 2; i <= n; i++) {
            f[i] = (i - 1LL) * (f[i - 1] + f[i - 2]) % mod;
        }
        return f[n];
    }
};

func findDerangement(n int) int {
    f := make([]int, n+1)
    f[0] = 1
    const mod = 1e9 + 7
    for i := 2; i <= n; i++ {
        f[i] = (i - 1) * (f[i-1] + f[i-2]) % mod
    }
    return f[n]
}

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)\).

Python3JavaC++Go

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

class Solution {
    public int findDerangement(int n) {
        final int mod = (int) 1e9 + 7;
        long a = 1, b = 0;
        for (int i = 2; i <= n; ++i) {
            long c = (i - 1) * (a + b) % mod;
            a = b;
            b = c;
        }
        return (int) b;
    }
}

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;
    }
};

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
}

Comments