Problem Description
Given an integer n, determine the number of derangements (i.e. permutations where no element appears in its original position) that can be generated from an array initially consisting of the numbers 1 through n in ascending order. Since the result can be very large, return it modulo 10^9 + 7.
Key Insights
- A derangement is a permutation where none of the elements appears in their original indices.
- Use the recurrence relation: D(n) = (n - 1) * (D(n - 1) + D(n - 2)) with base cases D(1) = 0 and D(2) = 1.
- Modular arithmetic is required at every computation step to handle large numbers.
- An iterative dynamic programming solution is efficient given the constraint n ≤ 10^6.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1) (using variables to store only the last two computed values)
Solution
The approach relies on dynamic programming with a recurrence relation derived from combinatorial reasoning. We set up two base cases: D(1) = 0 (there are no derangements for one element) and D(2) = 1 (there is exactly one derangement for two elements). For n > 2, we compute:
D(n) = (n - 1) * (D(n - 1) + D(n - 2)) modulo (10^9 + 7)
This recurrence works because:
- For any position, we can choose any of the remaining (n - 1) elements.
- After choosing an element for the first position, two cases arise: either the chosen element takes the first position (leading to D(n - 2)) or it doesn't (leading to D(n - 1)).
By iteratively updating the two last computed values, we can compute the final derangement count in O(n) time without requiring extra space for an array.