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:

datumu atšķirība programmā Excel

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

ⁿ

viendabīgs maisījums

).

Efektīvs risinājums

diāna ankudinova

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:

1. 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.
2. 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.
3. 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.
4. 
   
5. Tāpēc visu apakškopu pirmā elementa summa būs: SumF = a1.2
6. ^n-1
7. + a2.2
8. ^n-2
9. +...+ 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
10. ^n-1
11. Beidzot atbilde uz mūsu problēmu būs
12. SumL — SumF
13. .
14. Īstenošana:
15. 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('%dn' 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. ?> 

16. Izvade:

17. 21  
    

18. Laika sarežģītība: O(n) Šī raksta autors
19. Akašs Aggarvals
20. . Ja jums patīk GeeksforGeeks un vēlaties sniegt savu ieguldījumu, varat arī uzrakstīt rakstu, izmantojot
21. hozzájárulás.geeksforgeeks.org
22. vai nosūtiet savu rakstu pa e-pastu hozzájárulá[email protected]. Skatiet savu rakstu GeeksforGeeks galvenajā lapā un palīdziet citiem Geeks.