Suma de XOR de todos los subconjuntos posibles

Dada una array arr[] de tamaño n, necesitamos encontrar la suma de todos los valores que provienen de XORing todos los elementos de los subconjuntos. 

Input :  arr[] = {1, 5, 6}
Output : 28
Total Subsets = 23
1 = 1
5 = 5
6 = 6
1 ^ 5 = 4
1 ^ 6 = 7
5 ^ 6 = 3
1 ^ 5 ^ 6 = 2
0(empty subset)
Now SUM of all these XORs = 1 + 5 + 6 + 4 +
                            7 + 3 + 2 + 0
                          = 28

Input : arr[] = {1, 2}
Output : 6
 

Un enfoque ingenuo es tomar el XOR todas las combinaciones posibles de elementos de array [] y luego realizar la suma de todos los valores. La complejidad temporal de este enfoque crece exponencialmente, por lo que no sería mejor para un valor grande de n.

Implementación: código recursivo para el enfoque ingenuo

#include <bits/stdc++.h>
using namespace std;
int rec(int i, int x, int arr[], int size)
{
    // return the current xor sum if we reach the end of
    // array
    if (i == size)
        return x;
    // first choice can be to include the i-th element in
    // the subset and thus we take its xor
    int choice1 = rec(i + 1, x ^ arr[i], arr, size);
 
    // second choice can be to include the i-th element in
    // the subset and thus we take its xor
    int choice2 = rec(i + 1, x, arr, size);
 
    // return sum of both the choices as we need to find the
    // sum of xor of all subsets
    return choice1 + choice2;
}
// Returns sum of XORs of all subsets
int xorSum(int arr[], int size)
{
    return rec(0, 0, arr, size);
}
// Driver code
int main()
{
    int arr[] = { 1, 5, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << xorSum(arr, size);
}

// Java program to implement the approach
class GFG {
    static int rec(int i, int x, int arr[], int size)
    {
       
        // return the current xor sum if we reach the end of
        // array
        if (i == size)
            return x;
        // first choice can be to include the i-th element
        // in the subset and thus we take its xor
        int choice1 = rec(i + 1, x ^ arr[i], arr, size);
 
        // second choice can be to include the i-th element
        // in the subset and thus we take its xor
        int choice2 = rec(i + 1, x, arr, size);
 
        // return sum of both the choices as we need to find
        // the sum of xor of all subsets
        return choice1 + choice2;
    }
 
    // Returns sum of XORs of all subsets
    static int xorSum(int arr[], int size)
    {
        return rec(0, 0, arr, size);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 5, 6 };
        int size = arr.length;
       
          //Function call
        System.out.println(xorSum(arr, size));
    }
}
 
// This code is contributed by phasing17

# Python3 program to implement the approach
def rec(i, x, arr, size):
 
    # return the current xor sum if we reach the end of
    # array
    if (i == size):
        return x
       
    # first choice can be to include the i-th element in
    # the subset and thus we take its xor
    choice1 = rec(i + 1, x ^ arr[i], arr, size)
 
    # second choice can be to include the i-th element in
    # the subset and thus we take its xor
    choice2 = rec(i + 1, x, arr, size)
 
    # return sum of both the choices as we need to find the
    # sum of xor of all subsets
    return choice1 + choice2
 
# Returns sum of XORs of all subsets
def xorSum(arr, size):
    return rec(0, 0, arr, size)
 
# Driver code
arr = [1, 5, 6]
size = len(arr)
 
# Function call
print(xorSum(arr, size))
 
# This code is contributed by phasing17

// C# program to implement the approach
 
using System;
 
class GFG {
    static int rec(int i, int x, int[] arr, int size)
    {
 
        // return the current xor sum if we reach the end of
        // array
        if (i == size)
            return x;
        // first choice can be to include the i-th element
        // in the subset and thus we take its xor
        int choice1 = rec(i + 1, x ^ arr[i], arr, size);
 
        // second choice can be to include the i-th element
        // in the subset and thus we take its xor
        int choice2 = rec(i + 1, x, arr, size);
 
        // return sum of both the choices as we need to find
        // the sum of xor of all subsets
        return choice1 + choice2;
    }
 
    // Returns sum of XORs of all subsets
    static int xorSum(int[] arr, int size)
    {
        return rec(0, 0, arr, size);
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[] arr = { 1, 5, 6 };
        int size = arr.Length;
 
        // Function call
        Console.WriteLine(xorSum(arr, size));
    }
}
 
// This code is contributed by phasing17

<script>
 
    function rec(i, x, arr, size) {
        // Return the current xor sum if we reach the end of
        // array
        if (i == size)
            return x;
 
        // First choice can be to include the i-th element in
        // the subset and thus we take its xor
        let choice1 = rec(i + 1, x ^ arr[i], arr, size);
 
        // Second choice can be to include the i-th element in
        // the subset and thus we take its xor
        let choice2 = rec(i + 1, x, arr, size);
 
        // Return sum of both the choices as we need to find the
        // sum of xor of all subsets
        return choice1 + choice2;
    }
    // Returns sum of XORs of all subsets
    function xorSum(arr, size) {
        return rec(0, 0, arr, size);
    }
 
    // Driver code
    let arr = [ 1, 5, 6 ];
    let size = arr.length;
    document.write(xorSum(arr, size));
 
// This code is contributed by AshokJaiswal.
</script>

28

Un enfoque eficiente es encontrar el patrón con respecto a la propiedad de XOR. Ahora nuevamente considere el subconjunto en forma binaria como: 

    1 = 001
    5 = 101
    6 = 110
1 ^ 5 = 100
1 ^ 6 = 111
5 ^ 6 = 011
1^5^6 = 010

Entonces, si analizamos todos estos números binarios de los XOR, podemos observar que el bit establecido ocurre en todas las posiciones de i (0 a n-1) y contribuirá exactamente a la mitad de 2 ⁿ . Entonces podemos imponer fácilmente estas dos condiciones en cada posición de i. 

• Si hay algún valor de arr[] que tiene establecido i ^-ésimo bit establecido, entonces exactamente la mitad de 2 ⁿ subconjuntos tendrán la forma, por lo que contribuirán a 2 ^n-1+i a la suma final.
• Si no hay ningún valor de arr[] en el i ^-ésimo bit establecido, entonces podemos decir que no habrá ningún término en todos los subconjuntos que tengan el i ^-ésimo bit establecido.

La demostración del punto anterior es la siguiente:

Caso 1: 

• Supongamos que hay k elementos en la array con i ^-ésimo bit establecido y k no es cero. 
• Entonces, para tener un subconjunto con i-ésimo bit establecido en su xor, necesitamos que tenga un número impar de elementos con i ^-ésimo bit establecido.
• Número de formas de elegir elementos con i ^th bit no establecido = 2 ^(nk) 
• Número de formas de elegir elementos con i ^-ésimo conjunto de bits = ^k C ₁ + ^k C ₃ + ^k C ₅ …. = 2 ^(k-1)
• Número total de vías = 2 ^(n-1) 
• Por lo tanto, la contribución a la suma se convierte en 2 ^(n+i-1)

Caso 2: 

• Si ningún elemento tiene establecido el i ^-ésimo bit, es decir, k = 0, la contribución del i ^-ésimo bit a la suma total sigue siendo 0.
• Ahora la pregunta se reduce a verificar qué posición del elemento de arr[] se establecerá o no. Pero aquí hay un truco que no repetiremos para todos los elementos uno por uno a pesar de que podemos simplemente tomar el OR de todos esos valores y multiplicar con 2 ^n-1 , 

Por ejemplo 

Take a OR of all arr[] elements, we get 
= 1 | 5 | 6
= 001 | 101 | 110
= 111

Now to find final summation, we can write it down as:-
= 1*2n-1+2 + 1*2n-1+1 + 1*2n-1+0
= 2n-1 * (1*22 + 1*21 + 1*20 )
= 2n-1 * (1112)
= 2n-1 * 7

Put n = 3,  we get
= 28

Entonces, por fin, para cualquier valor de n y elementos de array, podemos decir que la suma final será 2 ^n-1 veces el OR bit a bit de todas las entradas.

// Below is C++ approach to finding the XOR_SUM
#include<bits/stdc++.h>
using namespace std;
 
// Returns sum of XORs of all subsets
int xorSum(int arr[], int n)
{
    int bits = 0;
 
    // Finding bitwise OR of all elements
    for (int i=0; i < n; ++i)
        bits |= arr[i];
 
    int ans = bits * pow(2, n-1);
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = {1, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << xorSum(arr, size);
}

// Java approach to finding the XOR_SUM
class GFG {
     
    // Returns sum of XORs of all subsets
    static int xorSum(int arr[], int n)
    {
         
        int bits = 0;
     
        // Finding bitwise OR of all elements
        for (int i = 0; i < n; ++i)
            bits |= arr[i];
     
        int ans = bits * (int)Math.pow(2, n-1);
     
        return ans;
    }
     
    // Driver method
    public static void main(String[] args)
    {
         
        int arr[] = {1, 5, 6};
        int size = arr.length;
         
        System.out.print(xorSum(arr, size));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 approach to finding the XOR_SUM
 
# Returns sum of XORs of all subsets
def xorSum(arr, n):
 
    bits = 0
 
    # Finding bitwise OR of all elements
    for i in range(n):
        bits |= arr[i]
 
    ans = bits * pow(2, n-1)
 
    return ans
 
# Driver Code
arr = [1, 5, 6]
size = len(arr)
print(xorSum(arr, size))
 
# This code is contributed by Anant Agarwal.

// C# approach to finding the XOR_SUM
using System;
 
class GFG {
     
    // Returns sum of XORs of all subsets
    static int xorSum(int []arr, int n)
    {
         
        int bits = 0;
     
        // Finding bitwise OR of all elements
        for (int i = 0; i < n; ++i)
            bits |= arr[i];
     
        int ans = bits * (int)Math.Pow(2, n - 1);
     
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
         
        int []arr = {1, 5, 6};
        int size = arr.Length;
         
        Console.Write(xorSum(arr, size));
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to finding the XOR_SUM
// Returns sum of XORs of all subsets
 
function xorSum($arr, $n)
{
    $bits = 0;
 
    // Finding bitwise OR
    // of all elements
    for ($i = 0; $i < $n; ++$i)
        $bits |= $arr[$i];
 
    $ans = $bits * pow(2, $n - 1);
 
    return $ans;
}
 
    // Driver code
    $arr = array(1, 5, 6);
    $size = sizeof($arr);
    echo xorSum($arr, $size);
 
// This code is contributed by nitin mittal.
?>

<script>
// Below is JavaScript approach to finding the XOR_SUM
 
// Returns sum of XORs of all subsets
function xorSum(arr, n)
{
    let bits = 0;
 
    // Finding bitwise OR of all elements
    for (let i=0; i < n; ++i)
        bits |= arr[i];
 
    let ans = bits * Math.pow(2, n-1);
 
    return ans;
}
 
// Driver code
 
    let arr = [1, 5, 6];
    let size = arr.length;
    document.write(xorSum(arr, size));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

28

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

Problemas relacionados: 
Dado un conjunto, encuentre el XOR de los XOR de todos los subconjuntos.  
Encuentra la suma de la suma de todas las subsecuencias

Este artículo es una contribución de Shubham Bansal . 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.