Find the Derangement of An Array - 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 of derangements it can generate.
Since the answer may be huge, return it modulo 109 + 7.
Input & Output
Example 1 — Small Case
$
Input:
n = 3
›
Output:
2
💡 Note:
Original array [1,2,3] has 2 derangements: [2,3,1] and [3,1,2]. In both cases, no element appears in its original position.
Example 2 — Base Case
$
Input:
n = 1
›
Output:
0
💡 Note:
With only one element [1], it's impossible to create a derangement since the element must go somewhere, and the only position is its original position.
Example 3 — Larger Case
$
Input:
n = 4
›
Output:
9
💡 Note:
For array [1,2,3,4], there are 9 valid derangements where no element is in its original position. Using formula: D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9
Constraints
- 1 ≤ n ≤ 1000
Visualization
Tap to expand
Understanding the Visualization
1
Input
Integer n representing array size [1,2,...,n]
2
Process
Count permutations where no element is in original position
3
Output
Number of valid derangements modulo 10^9 + 7
Key Takeaway
🎯 Key Insight: Use the recurrence relation D(n) = (n-1) × (D(n-1) + D(n-2)) for optimal O(n) solution
💡
Explanation
AI Ready
💡 Suggestion
Tab
to accept
Esc
to dismiss
// Output will appear here after running code