Question

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

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

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
}