إذا كانت المجموعة S مكونة من n أرقام، فأوجد مجموع الفرق بين العنصر الأخير والعنصر الأول في كل مجموعة فرعية. نجد العنصر الأول والأخير في كل مجموعة فرعية عن طريق الاحتفاظ بها بنفس الترتيب الذي تظهر فيه في مجموعة الإدخال S. أي sumSetDiff(S) = ? (الأخيرة (الأخيرة) - الأولى (الأخيرة)) حيث يمتد المجموع إلى جميع المجموعات الفرعية لـ S.

ملحوظة:

سايرا بانو الممثل

يجب أن تكون العناصر الموجودة في المجموعة الفرعية بنفس الترتيب الموجود في المجموعة S. أمثلة:

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.  

موصى به: الرجاء حلها على " يمارس 'أولاً قبل الانتقال إلى الحل.

حل بسيط

قائمة فرز جافا

لهذه المشكلة هي إيجاد الفرق بين العنصر الأخير والعنصر الأول لكل مجموعة فرعية من المجموعة S وإخراج مجموع هذه الاختلافات. التعقيد الزمني لهذا النهج هو O(2

^ن

).

هندسة جافا

حل فعال

لحل المشكلة في تعقيد الوقت الخطي. لقد حصلنا على مجموعة S تتكون من أرقام n ونحتاج إلى حساب مجموع الفرق بين العنصر الأخير والعنصر الأول لكل مجموعة فرعية من S، أي sumSetDiff(S) = ? (الأخيرة (الأخيرة) - الأولى (الأولى)) حيث يمتد المجموع إلى جميع المجموعات الفرعية لـ S. بشكل مكافئ sumSetDiff(S) = ? (الأخيرة (الأخيرة)) - ؟ (الأول (العناصر)) بمعنى آخر يمكننا حساب مجموع العنصر الأخير من كل مجموعة فرعية ومجموع العنصر الأول من كل مجموعة فرعية على حدة ثم حساب الفرق بينهما. لنفترض أن عناصر S هي {a1 a2 a3... an}. لاحظ الملاحظة التالية:

1. مجموعات فرعية تحتوي على عنصر a1 حيث يمكن الحصول على العنصر الأول عن طريق أخذ أي مجموعة فرعية من {a2 a3... an} ثم تضمين a1 فيها. سيكون عدد هذه المجموعات الفرعية 2^ن-1.
2. يمكن الحصول على المجموعات الفرعية التي تحتوي على العنصر a2 كعنصر أول عن طريق أخذ أي مجموعة فرعية من {a3 a4... an} ثم تضمين a2 فيها. سيكون عدد هذه المجموعات الفرعية 2^{ن -2}.
3. يمكن الحصول على المجموعات الفرعية التي تحتوي على العنصر ai كعنصر أول عن طريق أخذ أي مجموعة فرعية من {ai a(i+1)... an} ثم تضمين ai فيها. سيكون عدد هذه المجموعات الفرعية 2^ن-ط.
4. 
   
5. وبالتالي فإن مجموع العنصر الأول لجميع المجموعات الفرعية سيكون: SumF = a1.2
6. ^ن-1
7. + a2.2
8. ^{ن -2}
9. +...+ an.1 بطريقة مماثلة يمكننا حساب مجموع العنصر الأخير لجميع المجموعات الفرعية من S (مع الأخذ في كل خطوة ai كعنصر أخير بدلاً من العنصر الأول ثم الحصول على جميع المجموعات الفرعية). SumL = a1.1 + a2.2 +...+ an.2
10. ^ن-1
11. وأخيرا سيكون الجواب لمشكلتنا
12. SumL - SumF
13. .
14. تطبيق:
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. الإخراج:

17. 21  
    

18. تعقيد الوقت: O(n) ساهم في هذه المقالة
19. عكاش أغاروال
20. . إذا كنت تحب GeeksforGeeks وترغب في المساهمة، يمكنك أيضًا كتابة مقال باستخدام
21. تساهم.geeksforgeeks.org
22. أو أرسل مقالتك عبر البريد الإلكتروني إلى العنوان التالي:[email protected]. شاهد مقالتك التي تظهر على صفحة GeeksforGeeks الرئيسية وساعد المهوسون الآخرين.