# based on inclusion-exclusion rule solution, O(n) time, O(1) space

• If you couldn't remember the formula, I find these two videos really helpful.

With this formula, we can define P0 = #permutations that no number is in its original position.
P(one number) = #permutations one number is in its original position. C(n, 1) * (n-1)! = n!/1!
P(two number) = two are in their position. C(n, 2) * (n-2) ! = n!/2!
P(n numbers) = C(n, n) * (n-n)! = 1
It's also easy to see that:
P(m number) = n!/m! = (m+1)*P(m+1 number)

So based on the formula the number of cases when some number is in its own position is:
P(one number) - P(two number) + .... + (-1) ^(n+1) P(n number)
And all permutation of n numbers are n!
so P0 = n! - P(one number) + P(two numbers) + ..(-1)^n P(n numbers)

``````class Solution {
public:
const int M = 1e9 + 7;
int findDerangement(int n) {
long long res = 0;
long long pn = 1;
for(int i=n; i>=1; --i) {
res = ( res + (i % 2 == 0 ? 1 : -1) * pn + M)%M;
pn = pn * i % M;
}
return (pn + M + res)%M;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.