Suma de diferencias de subconjuntos

Posted on by Rudeus Greyrat

Dado un conjunto S que consta de n números, encuentre la suma de la diferencia entre el último y el primer elemento de cada subconjunto. Encontramos el primer y último elemento de cada subconjunto manteniéndolos en el mismo orden en que aparecen en el conjunto de entrada S.

es decir, sumSetDiff(S) = ∑ (último(s) – primero(s)),
donde sum cubre todos los subconjuntos s de S.

Nota: los elementos del subconjunto deben estar en el mismo orden que en el conjunto S.

Ejemplos:

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.

Una solución simple para este problema es encontrar la diferencia entre el último y el primer elemento para cada subconjunto s del conjunto S y generar la suma de todas estas diferencias. La complejidad del tiempo para este enfoque es O(2 n ).

Una solución eficiente para resolver el problema en la complejidad del tiempo lineal.
Tenemos un conjunto S que consta de n números, y necesitamos calcular la suma de la diferencia entre el último y el primer elemento de cada subconjunto de S, es decir,
sumSetDiff(S) = ∑ (último(s) – primero(s)) , donde sum cubre todos los subconjuntos s de S. De manera
equivalente,
sumSetDiff(S) = ∑ (último(s)) – ∑ (primero(s)),
En otras palabras, podemos calcular la suma del último elemento de cada subconjunto, y la suma del primer elemento de cada subconjunto por separado, y luego calcular su diferencia.

Digamos que los elementos de S son {a1, a2, a3,…, an}. Tenga en cuenta la siguiente observación:

  1. Los subconjuntos que contienen el elemento a1 como primer elemento se pueden obtener tomando cualquier subconjunto de {a2, a3,…, an} y luego incluyendo a1 en él. El número de tales subconjuntos será 2 n-1 .
  2. Los subconjuntos que contienen el elemento a2 como primer elemento se pueden obtener tomando cualquier subconjunto de {a3, a4,…, an} y luego incluyendo a2 en él. El número de tales subconjuntos será 2 n-2 .
  3. Los subconjuntos que contienen el elemento ai como primer elemento se pueden obtener tomando cualquier subconjunto de {ai, a(i+1),…, an} y luego incluyendo ai en él. El número de dichos subconjuntos será 2 n-i .

    4. Por tanto, la suma del primer elemento de todos los subconjuntos será:
    SumF = a1.2 n-1 + a2.2 n-2 +…+ an.1

    De manera similar, podemos calcular la suma del último elemento de todos los subconjuntos de S (Tomando en cada paso ai como último elemento en lugar de primer elemento y luego obteniendo todos los subconjuntos).
    SumaL = a1.1 + a2.2 +…+ an.2 n-1

    Finalmente, la respuesta de nuestro problema será SumL – SumF .

    Implementación:

    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\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.

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

    Producción:

    21

    Complejidad de tiempo : O(n)

    Este artículo es una contribución de Akash Aggarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

    Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *