based on inclusion-exclusion rule solution, O(n) time, O(1) space


  • 0
    Z

    If you couldn't remember the formula, I find these two videos really helpful.
    https://www.youtube.com/watch?v=51-b2mgZVNY
    https://www.youtube.com/watch?v=nwpzBE9IwJQ
    0_1503127824651_QQ图片20170810205706.png

    With this formula, we can define P0 = #permutations that no number is in its original position.
    P(one number) = #permutations one number is in its original position. C(n, 1) * (n-1)! = n!/1!
    P(two number) = two are in their position. C(n, 2) * (n-2) ! = n!/2!
    P(n numbers) = C(n, n) * (n-n)! = 1
    It's also easy to see that:
    P(m number) = n!/m! = (m+1)*P(m+1 number)

    So based on the formula the number of cases when some number is in its own position is:
    P(one number) - P(two number) + .... + (-1) ^(n+1) P(n number)
    And all permutation of n numbers are n!
    so P0 = n! - P(one number) + P(two numbers) + ..(-1)^n P(n numbers)

    class Solution {
    public:
        const int M = 1e9 + 7;
        int findDerangement(int n) {
            long long res = 0;
            long long pn = 1;
            for(int i=n; i>=1; --i) {
                res = ( res + (i % 2 == 0 ? 1 : -1) * pn + M)%M;
                pn = pn * i % M;
            }
            return (pn + M + res)%M;
        }
    };
    

Log in to reply
 

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