Problem statement

https://leetcode.com/problems/find-the-derangement-of-an-array/

Solution

Let $G_n$ be answer for $n$ numbers, then we can show, that $G_n = (n-1)\cdot(G_{n-1} + G_{n-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 $G_n = n\cdot G_{n-1} + (-1)^n$, which can be get, using classical inclusion-exclusion formula. Also we have formula $ n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}$

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