Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 634 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 634 # by problem number
lcpy gen -s find_the_derangement_of_an_array # by problem name
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 10^9 + 7.
Input: n = 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].
Input: n = 2
Output: 1
1 <= n <= 10^6class Solution:
# Time: O(n)
# Space: O(1)
def find_derangement(self, n: int) -> int:
mod = 1_000_000_007
if n == 1:
return 0
a, b = 1, 0 # D(1) = 0 carried via a = D(k-1)
for k in range(2, n + 1):
a, b = b, (k - 1) * (a + b) % mod
return b % mod
| Time | Space |
|---|---|
| O(n) | O(1) |