C++ 9ms


  • 0
    S

    Derangement recursion in Wiki

    #include <cmath>
    class Solution {
    public:
        int findDerangement(int n) {
            // recursion: !n = (n-1) * (!(n-1) + !(n-2))
            // base case: n is 1 or 2
            if (n == 1)
                return 0;
            if (n == 2)
                return 1;
            unsigned long long b = 1, a = 0, c = 0; // at least 64bits
            int k = 3;
            int m = (int)std::pow(10, 9) + 7;
            while (k <= n){
                c = ((k - 1) * (b + a)) % m;
                a = b;
                b = c;
                k += 1;
            } 
    		return (int)c;
        }
    };

Log in to reply
 

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