Problem

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 ofderangements it can generate. Since the answer may be huge, return it modulo 109 + 7.

Examples

Example 1:

1
2
3

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:

1
2

Input: n = 2
Output: 1

Constraints:

  • 1 <= n <= 10^6

Solution

Method 1 – Dynamic Programming (Derangement Recurrence)

Intuition

A derangement is a permutation where no element appears in its original position. The number of derangements for n elements, D(n), can be computed using the recurrence: D(n) = (n-1) * (D(n-1) + D(n-2)).

Approach

  1. Initialize D(0) = 1, D(1) = 0.
  2. For each i from 2 to n, compute D(i) = (i-1) * (D(i-1) + D(i-2)) modulo 10^9+7.
  3. Return D(n).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findDerangement(int n) {
        const int MOD = 1e9 + 7;
        if (n == 1) return 0;
        long long a = 1, b = 0, c;
        for (int i = 2; i <= n; ++i) {
            c = (long long)(i - 1) * (a + b) % MOD;
            a = b;
            b = c;
        }
        return b;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findDerangement(n int) int {
    MOD := int(1e9 + 7)
    if n == 1 {
        return 0
    }
    a, b := 1, 0
    for i := 2; i <= n; i++ {
        c := (i - 1) * (a + b) % MOD
        a, b = b, c
    }
    return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findDerangement(int n) {
        int MOD = 1_000_000_007;
        if (n == 1) return 0;
        long a = 1, b = 0, c = 0;
        for (int i = 2; i <= n; ++i) {
            c = (i - 1) * (a + b) % MOD;
            a = b;
            b = c;
        }
        return (int)b;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findDerangement(n: Int): Int {
        val MOD = 1_000_000_007
        if (n == 1) return 0
        var a = 1L
        var b = 0L
        for (i in 2..n) {
            val c = ((i - 1) * (a + b)) % MOD
            a = b
            b = c
        }
        return b.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findDerangement(self, n: int) -> int:
        MOD = 10**9 + 7
        if n == 1:
            return 0
        a, b = 1, 0
        for i in range(2, n+1):
            c = (i - 1) * (a + b) % MOD
            a, b = b, c
        return b
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn find_derangement(n: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;
        if n == 1 {
            return 0;
        }
        let (mut a, mut b) = (1i64, 0i64);
        for i in 2..=n as i64 {
            let c = (i - 1) * (a + b) % MOD;
            a = b;
            b = c;
        }
        b as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findDerangement(n: number): number {
        const MOD = 1e9 + 7;
        if (n === 1) return 0;
        let a = 1, b = 0;
        for (let i = 2; i <= n; ++i) {
            const c = (i - 1) * (a + b) % MOD;
            a = b;
            b = c;
        }
        return b;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we compute the answer iteratively up to n.
  • 🧺 Space complexity: O(1), as only a constant number of variables are used.