مجموع فروق المجموعات الفرعية

جربه على ممارسة GfG

#practiceLinkDiv { العرض: لا شيء! مهم؛ }

إذا كانت المجموعة 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}. لاحظ الملاحظة التالية:  
    مجموعات فرعية تحتوي على عنصر     a1    حيث يمكن الحصول على العنصر الأول عن طريق أخذ أي مجموعة فرعية من {a2 a3... an} ثم تضمين a1 فيها. سيكون عدد هذه المجموعات الفرعية 2  ^ن-1 .  
  يمكن الحصول على المجموعات الفرعية التي تحتوي على العنصر a2 كعنصر أول عن طريق أخذ أي مجموعة فرعية من {a3 a4... an} ثم تضمين a2 فيها. سيكون عدد هذه المجموعات الفرعية 2  ^{ن -2} .  
  يمكن الحصول على المجموعات الفرعية التي تحتوي على العنصر ai كعنصر أول عن طريق أخذ أي مجموعة فرعية من {ai a(i+1)... an} ثم تضمين ai فيها. سيكون عدد هذه المجموعات الفرعية 2  ^ن-ط .  
   
 
  وبالتالي فإن مجموع العنصر الأول لجميع المجموعات الفرعية سيكون: SumF = a1.2  
  ^ن-1 
  + a2.2  
  ^{ن -2} 
  +...+ an.1 بطريقة مماثلة يمكننا حساب مجموع العنصر الأخير لجميع المجموعات الفرعية من S (مع الأخذ في كل خطوة ai كعنصر أخير بدلاً من العنصر الأول ثم الحصول على جميع المجموعات الفرعية). SumL = a1.1 + a2.2 +...+ an.2  
  ^ن-1 
  وأخيرا سيكون الجواب لمشكلتنا  
     SumL - SumF    
  .  
     تطبيق:    
  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.   ?>   
   
  الإخراج:  
   21   
 
  تعقيد الوقت: O(n) ساهم في هذه المقالة  
     عكاش أغاروال    
  . إذا كنت تحب GeeksforGeeks وترغب في المساهمة، يمكنك أيضًا كتابة مقال باستخدام  
  تساهم.geeksforgeeks.org  
  أو أرسل مقالتك عبر البريد الإلكتروني إلى العنوان التالي:[email protected]. شاهد مقالتك التي تظهر على صفحة GeeksforGeeks الرئيسية وساعد المهوسون الآخرين.  
 
         إنشاء اختبار