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
C++
#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
// 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
# 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#
// 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
Javascript
<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>
Producción
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 n . 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 n 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 1 + k C 3 + k C 5 …. = 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.
C++
// 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
// 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
# 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#
// 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
// 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.
?>
Javascript
<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>
Producción
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.
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