Simple Solution Using DP Recurrence[with Explanation]


  • 0
    B
    int findDerangement(int n) {
          if(n == 1)return 0; 
         long a,b,c;
          a = 0;
          b = 1;
          
          //count(n) = (n-1)*(count(n-1) + count(n-2))
          /*
           There are n – 1 ways for element 1 (this explains multiplication with n-1).
    
    Let 1 be placed at index i. There are now two possibilities, depending on whether or not element i is placed at 1 or not.
    
    If i is placed at 1: This case is equivalent to solving the problem for n-2 elements as two elements have just swapped their positions.
    
    If i is not placed at 0: This case is equivalent to solving the problem for n-1 elements as now there are n-1 elements, n-1 positions and every element has n-2 choices
          
    
    */
          for(int i = 3; i <= n; i++){
              c = ((i-1)*(a + b)) % 1000000007;
              a = b % 1000000007;
              b = c % 1000000007;
          }
            return (int)b;
        }
    

Log in to reply
 

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