子集差异之和

给定一个由n个数组成的集合S，求每个子集的最后一个和第一个元素之间的差之和。我们通过使每个子集的第一个和最后一个元素保持与它们在输入集中出现的顺序相同的顺序来找到它们。

i、 东，萨姆塞迪夫（S）=∑ （最后一个–第一个）， 其中sum覆盖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.
{5,2}, last(s)-first(s) = -3.
{5,9}, last(s)-first(s) = 4.
{5,6}, last(s)-first(s) = 1.
{2,9}, last(s)-first(s) = 7.
{2,6}, last(s)-first(s) = 4.
{9,6}, last(s)-first(s) = -3.
{5,2,9}, last(s)-first(s) = 4.
{5,2,6}, last(s)-first(s) = 1.
{5,9,6}, last(s)-first(s) = 1.
{2,9,6}, last(s)-first(s) = 4.
{5,2,9,6}, last(s)-first(s) = 1.

Output  = -3+4+1+7+4-3+4+1+1+4+1
        = 21.

一个简单的解决方案 对于这个问题，要找到集合s的每个子集s的最后一个元素和第一个元素之间的差异，并输出这些差异的总和。这种方法的时间复杂度为O（2 ^N ).

有效的解决方案 解决线性时间复杂度问题。 给我们一个由n个数组成的集合S，我们需要计算S的每个子集的最后一个和第一个元素之间的差之和，即。， 萨姆塞迪夫(S)∑ （最后一个–第一个），其中总和覆盖s的所有子集。 相当地， 萨姆塞迪夫(S)∑ （最后几次）——∑ （一）， 换句话说，我们可以分别计算每个子集的最后一个元素和每个子集的第一个元素的和，然后计算它们的差。

假设S的元素是{a1，a2，a3，…，an}。注意以下观察结果：

1. 包含元素的子集 a1 因为第一个元素可以通过取{a2，a3，…，an}的任何子集，然后将a1包含进去而获得。此类子集的数量将为2 ^n-1 .
2. 将元素a2作为第一个元素的子集可以通过取{a3，a4，…，an}的任何子集，然后将a2包含进去而获得。此类子集的数量将为2 ^n-2 .
3. 包含元素ai作为第一个元素的子集可以通过取{ai，a（i+1），…，an}的任何子集，然后将ai包含在其中来获得。此类子集的数量将为2 ^n-i .

   因此，所有子集的第一个元素之和为： SumF=a1。2. ^n-1 +a2。2. ^n-2 +…+安。1.

   以类似的方式，我们可以计算S的所有子集的最后一个元素的和（在每一步将ai作为最后一个元素而不是第一个元素，然后获得所有子集）。 SumL=a1。1+a2。2+…+安。2. ^n-1

   最后，我们问题的答案是 SumL–SumF .

   实施：

   C++

   // A C++ program to find sum of difference between // last and first element of each subset #include<bits/stdc++.h> // 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" , 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.

   PHP

   <?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）

   本文由 阿卡什·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

   如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。