# JAVA and DP Solution with detailed explanation.

• ``````public int findDerangement(int n) {
if (n == 1) {
return 0;
}
long res = 1;
long lastRes = 0;
long lastLast = 0;
for (int i = 3; i <= n; i++) {
lastLast = lastRes;
lastRes = res;
res = (lastLast + lastRes % 1000000007) * (i - 1) % 1000000007;
}
return (int)(res % 1000000007);
}``````

• Explanation:
1, say we have n == 7, the number 1 can replace any of the 2 to 7, and each of that replacement is identical, so after we calculate the result, just multiply by 6.
2, now say we use 1 to replace 4, then for the number 4 alone, we have two options, either put 4 back to its position in 2, 3, 4, 5, 6, 7 which should the result of 6 numbers -> last result, or simply be disappeared, then we are left with 5 numbers 2, 3, 5, 6, 7 -> lastLast result. Then just add the two results together and multiply by 6, you will get the correct number
3, why DP? last is the result we calculated for k - 1 numbers, and lastLast is the result we calculated for k - 2 numbers

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