logo

TechCodeview

Summe der Teilmengenunterschiede

Probieren Sie es bei GfG Practice aus ' title= #practiceLinkDiv { display: none !important; }

Gegeben sei eine Menge S bestehend aus n Zahlen. Ermitteln Sie die Differenzsumme zwischen dem letzten und dem ersten Element jeder Teilmenge. Wir finden das erste und letzte Element jeder Teilmenge, indem wir sie in derselben Reihenfolge halten, in der sie im Eingabesatz S erscheinen, d. h. sumSetDiff(S) = ? (letzte(r) - erste(r)) wobei die Summe über alle Teilmengen s von S geht.

Notiz:

Java einschalten

Elemente in der Teilmenge sollten in der gleichen Reihenfolge sein wie in der Menge S. Beispiele:



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.

Empfohlen: Bitte lösen Sie es auf ' ÜBEN ' zuerst, bevor wir zur Lösung übergehen.

Eine einfache Lösung

Bei diesem Problem geht es darum, die Differenz zwischen dem letzten und dem ersten Element für jede Teilmenge s der Menge S zu ermitteln und die Summe aller dieser Differenzen auszugeben. Die Zeitkomplexität für diesen Ansatz beträgt O(2

N

Wert der Zeichenfolge

).

Eine effiziente Lösung

Sara Ali Khan Alter

um das Problem in linearer Zeitkomplexität zu lösen. Wir erhalten eine Menge S bestehend aus n Zahlen und müssen die Differenzsumme zwischen dem letzten und dem ersten Element jeder Teilmenge von S berechnen, d. h. sumSetDiff(S) = ? (letzte(r) - erste(r)) wobei die Summe über alle Teilmengen s von S geht. Äquivalent: sumSetDiff(S) = ? (letzte(r)) - ? (first(s)) Mit anderen Worten: Wir können die Summe des letzten Elements jeder Teilmenge und die Summe des ersten Elements jeder Teilmenge separat berechnen und dann ihre Differenz berechnen. Nehmen wir an, dass die Elemente von S {a1 a2 a3... an} sind. Beachten Sie die folgende Beobachtung:

  1. Teilmengen, die Elemente enthalten a1 als erstes Element kann erhalten werden, indem man eine beliebige Teilmenge von {a2 a3... an} nimmt und dann a1 darin einbezieht. Die Anzahl solcher Teilmengen beträgt 2n-1.
  2. Teilmengen, die das Element a2 als erstes Element enthalten, können erhalten werden, indem man eine beliebige Teilmenge von {a3 a4... an} nimmt und dann a2 darin einbezieht. Die Anzahl solcher Teilmengen beträgt 2n-2.
  3. Teilmengen, die das Element ai als erstes Element enthalten, können erhalten werden, indem man eine beliebige Teilmenge von {ai a(i+1)... an} nimmt und dann ai darin einbezieht. Die Anzahl solcher Teilmengen beträgt 2n-i.

  5. Daher beträgt die Summe des ersten Elements aller Teilmengen: SumF = a1.2
  6. n-1
  7. + a2.2
  8. n-2
  9. +...+ an.1 Auf ähnliche Weise können wir die Summe des letzten Elements aller Teilmengen von S berechnen (wobei wir bei jedem Schritt ai als letztes Element anstelle des ersten Elements nehmen und dann alle Teilmengen erhalten). SummeL = a1.1 + a2.2 +...+ an.2
  10. n-1
  11. Endlich wird die Antwort auf unser Problem sein
  12. SummeL - SummeF
  13. .
  14. Durchführung:
  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. Ausgabe:
  17. 21
  18. Zeitkomplexität: O(n) Dieser Artikel wurde verfasst von
  20. . Wenn Ihnen GeeksforGeeks gefällt und Sie einen Beitrag leisten möchten, können Sie auch einen Artikel über schreiben
  21. contributor.geeksforgeeks.org
  22. oder senden Sie Ihren Artikel per E-Mail an [email protected]. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.