[Java] 5 lines O(1) space solution


  • 11
    M

    Details can be found from wiki:
    https://en.wikipedia.org/wiki/Derangement#Counting_derangements

        private static final int M = 1000000007;
        public int findDerangement(int n) {
            long ans = 1;
            for (int i = 1; i <= n; i++) 
                ans = (i * ans % M + (i % 2 == 0 ? 1 : -1)) % M;
            return (int) ans;
        }
        
    

  • 1
    N

    Thanks for provide wiki link


  • 0
    B

    Very cool simplification of the formula on wikipedia. I tried playing around, and I see the similarities to a normal factorial, but don't know how to prove it. Would you be able to share the proof for why your formula works? Thanks!


  • 2

    @baselRus Denote E_n = D_n - n D_{n-1}.
    From the formula D_n = (n-1)(D_{n-1} + D_{n-2}), we have:

    E_n = -D_{n-1} + (n-1) (D_{n-2}) = -E_{n-1}.
    Together with E_0 = -1, this shows E_n = (-1)^n as desired.


  • 1
    B

    @awice Very cool, thanks!

    Just to write the result explicitly:

    We rewrite first line of @awice's proof, to get D_n = n D_{n-1} - E_n.
    Combine with last line of @awice's proof, we get D_n = n D_{n-1} - (-1)^n, which is the formula used in @MichaelPhelps' function.


  • 3
    S

    Here is my DP solution:
    For ith element, we have switch it with one of the previous numbers 1,2,...,i-1, and for each picked number j, for the positions left except the one take by i, j can take anyone of them. So there are dp[i - 2] permutation if j can take the original position of i, and dp[i - 1] permutations if j can not take the original position of i.

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

  • 0

    I also came up with a similar solution in C++. I have written my solution along with a verbose thought process to hopefully help other folks better understand this formula: https://discuss.leetcode.com/topic/102738/very-easy-to-understand-c-with-explanation


Log in to reply
 

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