# Java Solution With Explanation By Using Staggered formula

• The Staggered formula is D(n) = (n-1) [D(n-2) + D(n-1)]：

For the k th element, it has k-1 positions and there are two possibilities for its position

• 1.It's not in the first element, so it's going to be the same thing as D(n - 1)

• 2.It's in the position of the first element,so there are two elements in the deranged position.
So it's going to be the same thing as D(n - 2)

so res = ((i-1)(dn1+dn2))%1000000007;*
why we use long not int:
a(11) = 14684570
a(12) = 176214841
a(13) = 12 * (a(12) + a(11)) = 2290792932 > Integer.MAX_VALUE

`````` public int findDerangement(int n) {
long dn2 = 0, dn1 = 1;
long res = n==1 ? 0 : 1;
for (int i = 3; i <= n; i++){
res = ((i-1) * (dn1+dn2))%1000000007;
dn2 = dn1;
dn1 = res;
}
return (int) res;
}``````

• This post is deleted!

• Instead of using O(N) Space, We can do it in O(1)

``````public int findDerangement(int n){
long a = 0, b = 1;
long c = (n==0 || n==2) ? 1 : 0;
for (int i=3; i<=n; ++i){
c = ((i-1)*(b+a))%1000000007;
a = b;
b = c;
}
return (int) c;
}``````

• what do you mean first element

1.It's not in the first element,

2.It's in the position of the first element,s

• can somebody explain what statements below mean ?

1.It's not in the first element, so it's going to be the same thing as D(n - 1)

2.It's in the position of the first element,so there are two elements in the deranged position.
So it's going to be the same thing as D(n - 2)

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