# [Java] 5 lines O(1) space solution

• Details can be found from wiki:
https://en.wikipedia.org/wiki/Derangement#Counting_derangements

``````    private static final int M = 1000000007;
public int findDerangement(int n) {
long ans = 1;
for (int i = 1; i <= n; i++)
ans = (i * ans % M + (i % 2 == 0 ? 1 : -1)) % M;
return (int) ans;
}

``````

• Thanks for provide wiki link

• Very cool simplification of the formula on wikipedia. I tried playing around, and I see the similarities to a normal factorial, but don't know how to prove it. Would you be able to share the proof for why your formula works? Thanks!

• @baselRus Denote `E_n = D_n - n D_{n-1}`.
From the formula `D_n = (n-1)(D_{n-1} + D_{n-2})`, we have:

`E_n = -D_{n-1} + (n-1) (D_{n-2}) = -E_{n-1}`.
Together with `E_0 = -1`, this shows `E_n = (-1)^n` as desired.

• @awice Very cool, thanks!

Just to write the result explicitly:

We rewrite first line of @awice's proof, to get `D_n = n D_{n-1} - E_n`.
Combine with last line of @awice's proof, we get `D_n = n D_{n-1} - (-1)^n`, which is the formula used in @MichaelPhelps' function.

• Here is my DP solution:
For `ith` element, we have switch it with one of the previous numbers `1,2,...,i-1`, and for each picked number j, for the positions left except the one take by `i`, j can take anyone of them. So there are `dp[i - 2]` permutation if `j` can take the original position of `i`, and `dp[i - 1]` permutations if `j` can not take the original position of `i`.

``````public int findDerangement(int n) {
if(n <= 1) return 0;
long[] dp = new long[n + 1];
long mod = 1000000007;
dp[2] = 1;
for(int i = 3; i < dp.length; i++){
dp[i] = (long)(i - 1) * (dp[i - 1] + dp[i - 2]) % mod;
}
return (int)dp[dp.length - 1];
}
``````

• I also came up with a similar solution in C++. I have written my solution along with a verbose thought process to hopefully help other folks better understand this formula: https://discuss.leetcode.com/topic/102738/very-easy-to-understand-c-with-explanation

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