Java Solution With Explanation By Using Staggered formula


  • 8

    The Staggered formula is D(n) = (n-1) [D(n-2) + D(n-1)]:

    For the k th element, it has k-1 positions and there are two possibilities for its position

    • 1.It's not in the first element, so it's going to be the same thing as D(n - 1)

    • 2.It's in the position of the first element,so there are two elements in the deranged position.
      So it's going to be the same thing as D(n - 2)

    so res = ((i-1)(dn1+dn2))%1000000007;*
    why we use long not int:
    a(11) = 14684570
    a(12) = 176214841
    a(13) = 12 * (a(12) + a(11)) = 2290792932 > Integer.MAX_VALUE

     public int findDerangement(int n) {
            long dn2 = 0, dn1 = 1;
            long res = n==1 ? 0 : 1; 
            for (int i = 3; i <= n; i++){
                res = ((i-1) * (dn1+dn2))%1000000007;
                dn2 = dn1;
                dn1 = res;           
            }
            return (int) res;
        }

  • 0
    T
    This post is deleted!

  • 1
    A

    Instead of using O(N) Space, We can do it in O(1)

    public int findDerangement(int n){
        long a = 0, b = 1;
        long c = (n==0 || n==2) ? 1 : 0; 
        for (int i=3; i<=n; ++i){
            c = ((i-1)*(b+a))%1000000007;
            a = b;
            b = c;           
        }
        return (int) c;
    }

  • 0

    @aayushgarg Yeah, thk u for your advice:)


  • 0

    what do you mean first element

    1.It's not in the first element,

    2.It's in the position of the first element,s


  • 0
    T

    can somebody explain what statements below mean ?

    1.It's not in the first element, so it's going to be the same thing as D(n - 1)

    2.It's in the position of the first element,so there are two elements in the deranged position.
    So it's going to be the same thing as D(n - 2)


  • 0

Log in to reply
 

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