APAKŠKOPU ATŠĶIRĪBU SUMMA

Izmēģiniet to GfG Practice

#practiceLinkDiv { display: none !important; }

Dota kopa S, kas sastāv no n skaitļiem, atrodiet starpības summu starp katras apakškopas pēdējo un pirmo elementu. Mēs atrodam katras apakškopas pirmo un pēdējo elementu, saglabājot tos tādā pašā secībā, kādā tie parādās ievades kopā S. t.i., sumSetDiff(S) = ? (pēdējais(s) — pirmais(s)), kur summa iet pa visām S apakškopām.

Piezīme:

Elementiem apakškopā jābūt tādā pašā secībā kā komplektā S. Piemēri:

 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.   
   Ieteicams: lūdzu, atrisiniet to vietnē   PRAKSE   ' vispirms, pirms pāriet pie risinājuma.   
     Vienkāršs risinājums    
   Šī problēma ir atrast atšķirību starp pēdējo un pirmo elementu katrai kopas S apakškopai s un izvadīt visu šo atšķirību summu. Šīs pieejas laika sarežģītība ir O (2  
   ⁿ 
   ).  
      Efektīvs risinājums    
   atrisināt problēmu lineārā laika sarežģītībā. Mums ir dota kopa S, kas sastāv no n skaitļiem, un mums ir jāaprēķina starpības summa starp pēdējo un pirmo elementu katrā S apakškopā, t.i. sumSetDiff(S) = ? (pēdējais(s) - pirmais(s)), kur summa iet pa visām S apakškopām s. Līdzvērtīgi sumSetDiff(S) = ? (pēdējais(s)) - ? (pirmais(i)) Citiem vārdiem sakot, mēs varam aprēķināt katras apakškopas pēdējā elementa summu un katras apakškopas pirmā elementa summu atsevišķi un pēc tam aprēķināt to starpību. Pieņemsim, ka S elementi ir {a1 a2 a3... an}. Ņemiet vērā šādu novērojumu:  
    Apakškopas, kas satur elementu     a1    kā pirmo elementu var iegūt, ņemot jebkuru {a2 a3... an} apakškopu un pēc tam iekļaujot tajā a1. Šādu apakškopu skaits būs 2  ^n-1 .  
  Apakškopas, kas satur elementu a2 kā pirmo elementu, var iegūt, ņemot jebkuru {a3 a4... an} apakškopu un pēc tam iekļaujot tajā a2. Šādu apakškopu skaits būs 2  ^n-2 .  
  Apakškopas, kas satur elementu ai kā pirmo elementu, var iegūt, ņemot jebkuru {ai a(i+1)...an} apakškopu un pēc tam iekļaujot tajā ai. Šādu apakškopu skaits būs 2  ^n-i .  
   
 
  Tāpēc visu apakškopu pirmā elementa summa būs: SumF = a1.2  
  ^n-1 
  + a2.2  
  ^n-2 
  +...+ an.1 Līdzīgā veidā mēs varam aprēķināt visu S apakškopu pēdējā elementa summu (Katrā solī pieņemot ai kā pēdējo elementu, nevis pirmo elementu un pēc tam iegūstot visas apakškopas). SumL = a1.1 + a2.2 +...+ an.2  
  ^n-1 
  Beidzot atbilde uz mūsu problēmu būs  
     SumL — SumF    
  .  
     Īstenošana:    
  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.   ?>   
   
  Izvade:  
   21   
 
  Laika sarežģītība: O(n) Šī raksta autors  
     Akašs Aggarvals    
  . Ja jums patīk GeeksforGeeks un vēlaties sniegt savu ieguldījumu, varat arī uzrakstīt rakstu, izmantojot  
  hozzájárulás.geeksforgeeks.org  
  vai nosūtiet savu rakstu pa e-pastu hozzájárulá[email protected]. Skatiet savu rakstu GeeksforGeeks galvenajā lapā un palīdziet citiem Geeks.  
 
         Izveidojiet viktorīnu