Python, Straightforward with Explanation


  • 4
    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.


  • 0
    Q

    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]

  • 0
    Q

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


  • 0
    T

    Nice idea!
    Emulate your method:

    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;
        }
    }
    
    

  • 1

    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;


  • 0

    @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.


  • 0
    This post is deleted!

Log in to reply
 

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