O(n) Short Java Code


  • 2
    K

    Recursion Formula:
    D(n) = (n-1) [D(n-2) + D(n-1)]

    public class Solution {
        public int findDerangement(int n) {
            if (n<2) return 0;
            long f[]=new long[n+1];
            f[1]=0;f[2]=1;
            for (int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])*(i-1)%1000000007;
            return (int)f[n];
        }
    }
    

Log in to reply
 

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