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=(n1)(Gn1+Gn2), 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=nGn1+(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