[
math
dp
]
Leetcode 0634 Find the Derangement of An Array
Problem statement
https://leetcode.com/problems/find-the-derangement-of-an-array/
Solution
Let Gn be answer for n numbers, then we can show, that Gn=(n−1)⋅(Gn−1+Gn−2), which is not obvious: the idea is to arrange k to 1 and then we have two cases, either 1 arranged to k or not. There is another formula Gn=n⋅Gn−1+(−1)n, which can be get, using classical inclusion-exclusion formula. Also we have formula n!∑ni=0(−1)ii!
Complexity
Time complexity of all approaches is O(n)
.
Code
class Solution:
def findDerangement(self, n):
x, y = 1, 0
for n in range(2, n + 1):
x, y = y, (n - 1) * (x + y) % (10**9 + 7)
return y