SOM VAN SUBSETVERSCHILLEN

Probeer het eens op GfG Practice

#practiceLinkDiv {weergave: geen! belangrijk; }

Gegeven een verzameling S bestaande uit n getallen, zoek de som van het verschil tussen het laatste en het eerste element van elke deelverzameling. We vinden het eerste en het laatste element van elke subset door ze in dezelfde volgorde te houden als ze verschijnen in de invoerset S. d.w.z. sumSetDiff(S) = ? (laatste(n) - eerste(n)) waarbij de som over alle deelverzamelingen van S gaat.

Opmerking:

Elementen in de subset moeten in dezelfde volgorde staan als in de set S. Voorbeelden:

 S = {5 2 9 6} n = 4   
 Subsets are:   
 {5} last(s)-first(s) = 0.   
 {2} last(s)-first(s) = 0.   
 {9} last(s)-first(s) = 0.   
 {6} last(s)-first(s) = 0.   
 {52} last(s)-first(s) = -3.   
 {59} last(s)-first(s) = 4.   
 {56} last(s)-first(s) = 1.   
 {29} last(s)-first(s) = 7.   
 {26} last(s)-first(s) = 4.   
 {96} last(s)-first(s) = -3.   
 {529} last(s)-first(s) = 4.   
 {526} last(s)-first(s) = 1.   
 {596} last(s)-first(s) = 1.   
 {296} last(s)-first(s) = 4.   
 {5296} last(s)-first(s) = 1.   
 Output = -3+4+1+7+4-3+4+1+1+4+1   
  = 21.   
   Aanbevolen: los het op '   OEFENING   ' eerst voordat u verder gaat met de oplossing.   
     Een eenvoudige oplossing    
   want dit probleem is het vinden van het verschil tussen het laatste en het eerste element voor elke deelverzameling s van verzameling S en het uitvoeren van de som van ll deze verschillen. De tijdscomplexiteit voor deze benadering is O(2  
   ^N 
   ).  
      Een efficiënte oplossing    
   om het probleem in lineaire tijdscomplexiteit op te lossen. We krijgen een verzameling S die uit n getallen bestaat en we moeten de som van het verschil berekenen tussen het laatste en het eerste element van elke subset van S, d.w.z. sumSetDiff(S) = ? (laatste(n) - eerste(n)) waarbij de som over alle deelverzamelingen s van S gaat. Equivalent sumSetDiff(S) = ? (laatste(n)) - ? (eerste(n)) Met andere woorden: we kunnen de som van het laatste element van elke subset en de som van het eerste element van elke subset afzonderlijk berekenen en vervolgens hun verschil berekenen. Laten we zeggen dat de elementen van S {a1 a2 a3... an} zijn. Let op de volgende observatie:  
    Subsets die een element bevatten     een1    aangezien het eerste element kan worden verkregen door een deelverzameling van {a2 a3... an} te nemen en er vervolgens a1 in op te nemen. Het aantal van dergelijke subsets zal 2 zijn  ^n-1 .  
  Deelverzamelingen die element a2 als eerste element bevatten, kunnen worden verkregen door een deelverzameling van {a3 a4... an} te nemen en daar vervolgens a2 in op te nemen. Het aantal van dergelijke subsets zal 2 zijn  ^n-2 .  
  Subsets die element ai als eerste element bevatten, kunnen worden verkregen door een subset van {ai a(i+1)... an} te nemen en daar vervolgens ai in op te nemen. Het aantal van dergelijke subsets zal 2 zijn  ^n-ik .  
   
 
  Daarom zal de som van het eerste element van alle subsets zijn: SumF = a1.2  
  ^n-1 
  + een2.2  
  ^n-2 
  +...+ an.1 Op soortgelijke wijze kunnen we de som van het laatste element van alle deelverzamelingen van S berekenen (bij elke stap ai als laatste element nemen in plaats van het eerste element en dan alle deelverzamelingen verkrijgen). SomL = a1,1 + a2,2 +...+ an.2  
  ^n-1 
  Eindelijk zal het antwoord op ons probleem zijn  
     SomL - SomF    
  .  
     Uitvoering:    
  C++      // A C++ program to find sum of difference between   // last and first element of each subset   #include       // Returns the sum of first elements of all subsets   int     SumF  (  int     S  []     int     n  )   {      int     sum     =     0  ;      // Compute the SumF as given in the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  S  [  i  ]     *     pow  (  2       n  -  i  -1  ));      return     sum  ;   }   // Returns the sum of last elements of all subsets   int     SumL  (  int     S  []     int     n  )   {      int     sum     =     0  ;      // Compute the SumL as given in the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  S  [  i  ]     *     pow  (  2       i  ));      return     sum  ;   }   // Returns the difference between sum of last elements of   // each subset and the sum of first elements of each subset   int     sumSetDiff  (  int     S  []     int     n  )   {      return     SumL  (  S       n  )     -     SumF  (  S       n  );   }   // Driver program to test above function   int     main  ()   {      int     n     =     4  ;      int     S  []     =     {  5       2       9       6  };      printf  (  '%d  n  '       sumSetDiff  (  S       n  ));      return     0  ;   }   
  Java      // A Java program to find sum of difference    // between last and first element of each    // subset   class   GFG     {          // Returns the sum of first elements       // of all subsets      static     int     SumF  (  int     S  []       int     n  )      {      int     sum     =     0  ;      // Compute the SumF as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *         Math  .  pow  (  2       n     -     i     -     1  ));      return     sum  ;      }      // Returns the sum of last elements       // of all subsets      static     int     SumL  (  int     S  []       int     n  )      {      int     sum     =     0  ;      // Compute the SumL as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *      Math  .  pow  (  2       i  ));          return     sum  ;      }      // Returns the difference between sum       // of last elements of each subset and       // the sum of first elements of each       // subset      static     int     sumSetDiff  (  int     S  []       int     n  )      {      return     SumL  (  S       n  )     -     SumF  (  S       n  );      }      // Driver program      public     static     void     main  (  String     arg  []  )      {      int     n     =     4  ;      int     S  []     =     {     5       2       9       6     };          System  .  out  .  println  (  sumSetDiff  (  S       n  ));      }   }   // This code is contributed by Anant Agarwal.   
  Python3      # Python3 program to find sum of   # difference between last and    # first element of each subset   # Returns the sum of first   # elements of all subsets   def   SumF  (  S     n  ):   sum   =   0   # Compute the SumF as given   # in the above explanation   for   i   in   range  (  n  ):   sum   =   sum   +   (  S  [  i  ]   *   pow  (  2     n   -   i   -   1  ))   return   sum   # Returns the sum of last   # elements of all subsets   def   SumL  (  S     n  ):   sum   =   0   # Compute the SumL as given   # in the above explanation   for   i   in   range  (  n  ):   sum   =   sum   +   (  S  [  i  ]   *   pow  (  2     i  ))   return   sum   # Returns the difference between sum   # of last elements of each subset and   # the sum of first elements of each subset   def   sumSetDiff  (  S     n  ):   return   SumL  (  S     n  )   -   SumF  (  S     n  )   # Driver program   n   =   4   S   =   [  5     2     9     6  ]   print  (  sumSetDiff  (  S     n  ))   # This code is contributed by Anant Agarwal.   
  C#         // A C# program to find sum of difference    // between last and first element of each    // subset   using     System  ;   class     GFG     {          // Returns the sum of first elements       // of all subsets      static     int     SumF  (  int     []  S       int     n  )      {      int     sum     =     0  ;          // Compute the SumF as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *         Math  .  Pow  (  2       n     -     i     -     1  ));      return     sum  ;      }          // Returns the sum of last elements       // of all subsets      static     int     SumL  (  int     []  S       int     n  )      {      int     sum     =     0  ;          // Compute the SumL as given in       // the above explanation      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      sum     =     sum     +     (  int  )(  S  [  i  ]     *      Math  .  Pow  (  2       i  ));          return     sum  ;      }          // Returns the difference between sum       // of last elements of each subset and       // the sum of first elements of each       // subset      static     int     sumSetDiff  (  int     []  S       int     n  )      {      return     SumL  (  S       n  )     -     SumF  (  S       n  );      }          // Driver program      public     static     void     Main  ()      {      int     n     =     4  ;      int     []  S     =     {     5       2       9       6     };          Console  .  Write  (  sumSetDiff  (  S       n  ));      }   }       // This code is contributed by nitin mittal.   
  JavaScript      // Returns the sum of first elements of all subsets   function     sumF  (  S       n  )     {      let     sum     =     0  ;      // Compute the SumF as given in the above explanation      for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )     {      sum     +=     S  [  i  ]     *     Math  .  pow  (  2       n     -     i     -     1  );      }      return     sum  ;   }   // Returns the sum of last elements of all subsets   function     sumL  (  S       n  )     {      let     sum     =     0  ;      // Compute the SumL as given in the above explanation      for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )     {      sum     +=     S  [  i  ]     *     Math  .  pow  (  2       i  );      }      return     sum  ;   }   // Returns the difference between sum of last elements of each subset and the sum of first elements of each subset   function     sumSetDiff  (  S       n  )     {      return     sumL  (  S       n  )     -     sumF  (  S       n  );   }   // Driver program to test the above functions   function     main  ()     {      const     n     =     4  ;      const     S     =     [  5       2       9       6  ];      console  .  log  (  sumSetDiff  (  S       n  ));   }   main  ();   
  PHP         // A PHP program to find sum    // of difference between last    // and first element of each subset   // Returns the sum of first    // elements of all subsets   function   SumF  (   $S     $n  )   {   $sum   =   0  ;   // Compute the SumF as given    // in the above explanation   for   (  $i   =   0  ;   $i    <   $n  ;   $i  ++  )   $sum   =   $sum   +   (  $S  [  $i  ]   *   pow  (  2     $n   -   $i   -   1  ));   return   $sum  ;   }   // Returns the sum of last   // elements of all subsets   function   SumL  (   $S     $n  )   {   $sum   =   0  ;   // Compute the SumL as given   // in the above explanation   for  (  $i   =   0  ;   $i    <   $n  ;   $i  ++  )   $sum   =   $sum   +   (  $S  [  $i  ]   *   pow  (  2     $i  ));   return   $sum  ;   }   // Returns the difference between   // sum of last elements of   // each subset and the sum of   // first elements of each subset   function   sumSetDiff  (   $S     $n  )   {   return   SumL  (  $S     $n  )   -   SumF  (  $S     $n  );   }   // Driver Code   $n   =   4  ;   $S   =   array  (  5     2     9     6  );   echo   sumSetDiff  (  $S     $n  );   // This code is contributed by anuj_67.   ?>   
   
  Uitgang:  
   21   
 
  Tijdcomplexiteit: O(n) Dit artikel is bijgedragen door  
     Akash Aggarwal    
  . Als je GeeksforGeeks leuk vindt en een bijdrage wilt leveren, kun je ook een artikel schrijven met  
  bijdrage.geeksforgeeks.org  
  of mail uw artikel naar [email protected]. Zie uw artikel verschijnen op de hoofdpagina van GeeksforGeeks en help andere Geeks.  
 
         Quiz maken