Suma diferențelor de subgrup
Încercați-l pe GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Având în vedere o mulțime S formată din n numere, găsiți suma diferenței dintre ultimul și primul element al fiecărei submulțimi. Găsim primul și ultimul element din fiecare submulțime păstrându-le în aceeași ordine în care apar în setul de intrare S. adică sumSetDiff(S) = ? (ultimul(i) - primul(ii)) unde suma trece peste toate submulțimile s din S.
Nota:
Elementele din submulțime ar trebui să fie în aceeași ordine ca în mulțimea S. Exemple:
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.
Recomandat: Vă rugăm să rezolvați-l pe „ PRACTICA ' mai întâi înainte de a trece la soluție.
O soluție simplă
deoarece această problemă este de a găsi diferența dintre ultimul și primul element pentru fiecare submulțime s din mulțimea S și de a obține suma tuturor acestor diferențe. Complexitatea timpului pentru această abordare este O(2
n
).
O solutie eficienta
pentru a rezolva problema în complexitate liniară de timp. Ni se oferă o mulțime S formată din n numere și trebuie să calculăm suma diferenței dintre ultimul și primul element al fiecărei submulțimi a lui S, adică sumSetDiff(S) = ? (last(s) - first(s)) unde suma trece peste toate submulțimile lui S. În mod echivalent sumSetDiff(S) = ? (ultimele) - ? (primul(ii)) Cu alte cuvinte, putem calcula separat suma ultimului element al fiecărei submulțimi și suma primului element al fiecărei submulțimi separat și apoi putem calcula diferența lor. Să spunem că elementele lui S sunt {a1 a2 a3... an}. Rețineți următoarea observație:
Creați un test
- Subseturi care conțin element a1 ca primul element poate fi obținut prin luarea oricărui submulț al lui {a2 a3... an} și apoi incluzând a1 în el. Numărul de astfel de subseturi va fi 2 n-1 .
- Subseturile care conțin elementul a2 ca prim element pot fi obținute luând orice submulțime de {a3 a4... an} și apoi incluzând a2 în el. Numărul de astfel de subseturi va fi 2 n-2 .
- Subseturile care conțin elementul ai ca prim element pot fi obținute luând orice submulțime de {ai a(i+1)... an} și apoi incluzând ai în el. Numărul de astfel de subseturi va fi 2 n-i .
- Prin urmare, suma primului element al tuturor submulților va fi: SumF = a1.2
- n-1
- + a2.2
- n-2
- +...+ an.1 În mod similar putem calcula suma ultimului element din toate submulțimile lui S (luând la fiecare pas ai ca ultim element în loc de prim element și apoi obținând toate submulțimile). SumL = a1.1 + a2.2 +...+ an.2
- n-1
- În cele din urmă, răspunsul la problema noastră va fi
- SumL - SumF
- .
- Implementare:
- C++
Java// 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 ; } Python3// 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.C## 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.JavaScript// 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// 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 ();- Ieșire:
- Complexitatea timpului: O(n) Acest articol este contribuit de
- Akash Aggarwal
- . Dacă vă place GeeksforGeeks și doriți să contribui, puteți scrie și un articol folosind
- contribute.geeksforgeeks.org
- sau trimiteți articolul la [email protected]. Vedeți articolul dvs. care apare pe pagina principală GeeksforGeeks și ajutați alți Geeks.
