# Python, Straightforward with Explanation

• ``````def findDerangement(self, N):
MOD = 10**9 + 7
X, Y = 1, 0
for n in xrange(2, N+1):
X, Y = Y, (n - 1) * (X + Y) % MOD
return Y
``````

Let `D(N)` be the required answer. The recursion for the number of derangements of N is: `D(N) = (N-1) * (D(N-1) + D(N-2))`. With this recursion in hand, the problem becomes similar to finding the N-th fibonacci number.

To prove it, suppose there are people and hats labelled `1...N`. We want the number of ways to put a hat on each person such that no person is wearing their hat. The first person has N-1 choices to put on a hat, say he wears hat X. Now consider what hat person X is wearing. Either he takes hat 1, and we have `D(N-2)` ways to arrange the remaining hats among people; or he doesn't take hat 1, which if we relabelled it as hat X, would have `D(N-1)` ways to arrange the remaining hats.

• Why am I Time Limit Exeed

``````    a = [0 for _ in range(1000050)]
a[1], a[2], a[3] = 0, 1, 2
for i in range(4, n+1):
a[i] = ((i-1)*(a[i-2]+a[i-1]))%(1000000007)
return a[n]``````

• a = [0]*1000050 has less time than a = [0 for _ in range(1000050)]

• Nice idea!

``````public class Solution {
public int findDerangement(int n) {
if(n==1) return 0;
if(n==2) return 1;

//long[] dp=new long[n+1];
long mod=(long)(1e9+7);

long x=0,y=1;
for(int i=3;i<=n;i++){
long sum=(i-1)*(x+y)%mod;
x=y;
y=sum;
}
return (int)y;
}
}

``````

• A little more explanation:

For the original D(n-1) problem, each person in 1 -- n-1 may get his own hat, so each person (including person x) only have n-2 choices;

For the D(n) problem:
While after the first person pick the Hat X, there are n-1 persons left , all persons left other than X have n-2 choices, and person X have n-1 choices;

And for person X: if x pick some hat other than hat_1, means X also only have n-2 choices. n-1 persons and each has n-2 choices == D(n-1) problem;
if x pick hat_1, than there are only n-2 persons left, and each has n-3 choices == D(n-2) prolbem;

• @qsj why did you do so? for n = 1, you also assign such an array for it. Then, of course it will lead to TLE.

• This post is deleted!

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