Find the Derangement of An Array

Problem Statement

In the field of combinatorial mathematics, derangement refers to a specific type of permutation where no element is allowed to appear in its original position. Given a number n, you start with an array formed by integers from 1 to n in ascending order. The challenge is to determine how many such permutations (derangements) of this array are possible where no element remains in its initial position. Due to the potentially large size of the result, it should be returned modulo 10^9 + 7.

Examples

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

Approach and Intuition

Understanding the problem revolves around appreciating the idea of derangements or permutations where elements cannot remain in their original positions. Here's how we conceptualize our approach to solving this:

1. Understanding Permutations:

   • A permutation is any rearrangement of elements. In our problem, with the restriction that no element is in its initial position, these are special permutations.

2. Base Cases Analysis:

   • For n = 1 there's only one array, [1], and no derangement exists since the solitary element must stay in position.
   • For n = 2, the possible arrays are [1,2] and [2,1]. However, only [2,1] is a derangement.

3. Pattern and Recurrence Recognition:

   • An essential part of solving a computationally intense problem like this, especially with constraints as large as 1 <= n <= 10^6, lies in recognizing patterns or recurrence relations:
   • From earlier combinatorial studies, the count of derangements for an array can use the recurrence relation:
     • D(n) = (n - 1) * (D(n - 1) + D(n - 2))
   • This recurrence efficiently build the solution up from base cases using past computed results.

4. Implementation Steps:

   • Create an array say dp, where dp[i] holds the number of derangements for an array of length i.
   • Initialize the first few base cases:
     • dp[1] = 0 since no derangement is possible.
     • dp[2] = 1 considering the derangement as [2, 1].
   • Use the recurrence relation to fill in the rest of the values up to dp[n].
     • For each i from 3 to n, compute dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) modulo 10^9 + 7.
   • The resulting dp[n] will be the count of derangements modulo 10^9 + 7.

By rigorously analyzing and applying fundamental principles of combinatorics, and then utilizing dynamic programming to efficiently calculate large sequences, we can obtain the answer for large values of n without direct enumeration, which would be computationally prohibitive.

Solutions

public class Solution {
    public int calculateDerangement(int n) {
        long product = 1, total = 0, MOD = 1000000007;
        for (int i = n; i >= 0; i--) {
            total = (total + MOD + product * (i % 2 == 0 ? 1 : -1)) % MOD;
            product = (product * i) % MOD;
        }
        return (int) total;
    }
}