Find the derangement of an array

Math Dynamic Programming Combinatorics

41.6% acceptance

Mar 31, 2026

223

167

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_derangement(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    if n == 1 { return 0; }
    if n == 2 { return 1; }
    let mut prev2: i64 = 0; // D(1)
    let mut prev1: i64 = 1; // D(2)
    for i in 3..=n as i64 {
      let cur = (i - 1) * (prev1 + prev2) % MOD;
      prev2 = prev1;
      prev1 = cur;
    }
    prev1 as i32
  }
}