Dada una array que contiene N enteros positivos, la tarea es encontrar la suma de XOR de todas las subarreglas de la array.
Ejemplos:
Input : arr[] = {1, 3, 7, 9, 8, 7}
Output : 128
Input : arr[] = {3, 8, 13}
Output : 46
Explanation for second test-case:
XOR of {3} = 3
XOR of {3, 8} = 11
XOR of {3, 8, 13} = 6
XOR of {8} = 8
XOR of {8, 13} = 5
XOR of {13} = 13
Sum = 3 + 11 + 6 + 8 + 5 + 13 = 46
Solución simple: una solución simple será generar todos los subconjuntos y luego iterarlos todos para encontrar los valores XOR requeridos y luego resumirlos. La complejidad temporal de este enfoque será O(n 3 ).
Mejor solución: una mejor solución será usar una array de prefijos, es decir, para cada índice ‘i’ de la array ‘arr[]’, cree una array de prefijos para almacenar el XOR de todos los elementos del extremo izquierdo de la array ‘arr[ ]’ hasta el i -ésimo elemento de ‘arr[]’. La creación de una array de prefijos llevará un tiempo de O(N).
Ahora, usando esta array de prefijos, podemos encontrar el valor XOR de cualquier sub-array en tiempo O(1).
Podemos encontrar el XOR del índice l a r usando la fórmula:
if l is not zero
XOR = prefix[r] ^ prefix[l-1]
else
XOR = prefix[r].
Después de esto, todo lo que tenemos que hacer es, en resumen, los valores XOR de todos los sub-arreglos.
Dado que el número total de subarreglos es del orden (N 2 ) , la complejidad temporal de este enfoque será O(N 2 ).
Mejor solución: en aras de una mejor comprensión, supongamos que cualquier parte de un elemento está representada por la variable ‘i’ y la variable ‘suma’ se usa para almacenar la suma final.
La idea aquí es que intentaremos encontrar el número de valores XOR con i -ésimo conjunto de bits. Supongamos que hay un número ‘S i ‘ de subarrays con i -ésimo conjunto de bits. Para, i th bit, la suma se puede actualizar como sum += (2 i * S).
Entonces, la pregunta es ¿cómo implementar la idea anterior?
Dividiremos la tarea en varios pasos. En cada paso, intentaremos encontrar el número de valores XOR con i -ésimo bit establecido.
Ahora, dividiremos cada paso en subpasos. En cada subpaso, intentaremos encontrar el número de subarreglos a partir de un índice ‘j’ (donde j varía entre 0 y n – 1) con i -ésimo bit establecido en su valor XOR. Para establecer el i -ésimo bit, un número impar de elementos de la sub-array debería tener el i -ésimo bit establecido.
Para todos los bits, en una variable c_odd, almacenaremos el recuento del número de subarreglos a partir de j = 0 con i thbit establecido en un número impar de elementos. Luego, iteraremos a través de todos los elementos de la array actualizando el valor de c_odd cuando sea necesario. Si llegamos a un elemento ‘j’ con i -ésimo conjunto de bits, actualizaremos c_odd como c_odd = (n – j – c_odd) . Se debe a que, dado que encontramos un bit establecido, el número de subarreglos con un número par de elementos con i -ésimo bit cambiará a un número de subarreglos con un número impar de elementos con i -ésimo bit establecido.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find the sum of XOR of
// all subarray of the array
#include <iostream>
#include <vector>
using namespace std;
// Function to calculate the sum of XOR
// of all subarrays
int findXorSum(int arr[], int n)
{
// variable to store
// the final sum
int sum = 0;
// multiplier
int mul = 1;
for (int i = 0; i < 30; i++) {
// variable to store number of
// sub-arrays with odd number of elements
// with ith bits starting from the first
// element to the end of the array
int c_odd = 0;
// variable to check the status
// of the odd-even count while
// calculating c_odd
bool odd = 0;
// loop to calculate initial
// value of c_odd
for (int j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
odd = (!odd);
if (odd)
c_odd++;
}
// loop to iterate through
// all the elements of the
// array and update sum
for (int j = 0; j < n; j++) {
sum += (mul * c_odd);
if ((arr[j] & (1 << i)) > 0)
c_odd = (n - j - c_odd);
}
// updating the multiplier
mul *= 2;
}
// returning the sum
return sum;
}
// Driver Code
int main()
{
int arr[] = { 3, 8, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findXorSum(arr, n);
return 0;
}
Java
// Java program to find the sum of XOR
// of all subarray of the array
import java.util.*;
class GFG
{
// Function to calculate the sum of XOR
// of all subarrays
static int findXorSum(int arr[], int n)
{
// variable to store
// the final sum
int sum = 0;
// multiplier
int mul = 1;
for (int i = 0; i < 30; i++)
{
// variable to store number of
// sub-arrays with odd number of elements
// with ith bits starting from the first
// element to the end of the array
int c_odd = 0;
// variable to check the status
// of the odd-even count while
// calculating c_odd
boolean odd = false;
// loop to calculate initial
// value of c_odd
for (int j = 0; j < n; j++)
{
if ((arr[j] & (1 << i)) > 0)
odd = (!odd);
if (odd)
c_odd++;
}
// loop to iterate through
// all the elements of the
// array and update sum
for (int j = 0; j < n; j++)
{
sum += (mul * c_odd);
if ((arr[j] & (1 << i)) > 0)
c_odd = (n - j - c_odd);
}
// updating the multiplier
mul *= 2;
}
// returning the sum
return sum;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 8, 13 };
int n = arr.length;
System.out.println(findXorSum(arr, n));
}
}
// This code is contributed by Rituraj Jain.
Python3
# Python3 program to find the Sum of # XOR of all subarray of the array # Function to calculate the Sum of XOR # of all subarrays def findXorSum(arr, n): # variable to store the final Sum Sum = 0 # multiplier mul = 1 for i in range(30): # variable to store number of sub-arrays # with odd number of elements with ith # bits starting from the first element # to the end of the array c_odd = 0 # variable to check the status of the # odd-even count while calculating c_odd odd = 0 # loop to calculate initial # value of c_odd for j in range(n): if ((arr[j] & (1 << i)) > 0): odd = (~odd) if (odd): c_odd += 1 # loop to iterate through all the # elements of the array and update Sum for j in range(n): Sum += (mul * c_odd) if ((arr[j] & (1 << i)) > 0): c_odd = (n - j - c_odd) # updating the multiplier mul *= 2 # returning the Sum return Sum # Driver Code arr = [3, 8, 13] n = len(arr) print(findXorSum(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# program to find the sum of XOR of
// all subarray of the array
using System;
class GFG
{
// Function to calculate the sum
// of XOR of all subarrays
static int findXorSum(int []arr, int n)
{
// variable to store
// the final sum
int sum = 0;
// multiplier
int mul = 1;
for (int i = 0; i < 30; i++)
{
// variable to store number of sub-arrays
// with odd number of elements with ith
// bits starting from the first element
// to the end of the array
int c_odd = 0;
// variable to check the status
// of the odd-even count while
// calculating c_odd
bool odd = false;
// loop to calculate initial
// value of c_odd
for (int j = 0; j < n; j++)
{
if ((arr[j] & (1 << i)) > 0)
odd = (!odd);
if (odd)
c_odd++;
}
// loop to iterate through
// all the elements of the
// array and update sum
for (int j = 0; j < n; j++)
{
sum += (mul * c_odd);
if ((arr[j] & (1 << i)) > 0)
c_odd = (n - j - c_odd);
}
// updating the multiplier
mul *= 2;
}
// returning the sum
return sum;
}
// Driver Code
static void Main()
{
int []arr = { 3, 8, 13 };
int n = arr.Length;
Console.WriteLine(findXorSum(arr, n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find the sum of XOR
// of all subarray of the array
// Function to calculate the sum of
// XOR of all subarrays
function findXorSum($arr, $n)
{
// variable to store
// the final sum
$sum = 0;
// multiplier
$mul = 1;
for ($i = 0; $i < 30; $i++)
{
// variable to store number of
// sub-arrays with odd number of
// elements with ith bits starting
// from the first element to the
// end of the array
$c_odd = 0;
// variable to check the status
// of the odd-even count while
// calculating c_odd
$odd = 0;
// loop to calculate initial
// value of c_odd
for ($j = 0; $j < $n; $j++)
{
if (($arr[$j] & (1 << $i)) > 0)
$odd = (!$odd);
if ($odd)
$c_odd++;
}
// loop to iterate through
// all the elements of the
// array and update sum
for ($j = 0; $j < $n; $j++)
{
$sum += ($mul * $c_odd);
if (($arr[$j] & (1 << $i)) > 0)
$c_odd = ($n - $j - $c_odd);
}
// updating the multiplier
$mul *= 2;
}
// returning the sum
return $sum;
}
// Driver Code
$arr = array(3, 8, 13);
$n = sizeof($arr);
echo findXorSum($arr, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to find
// the sum of XOR of
// all subarray of the array
// Function to calculate the sum of XOR
// of all subarrays
function findXorSum(arr, n)
{
// variable to store
// the final sum
let sum = 0;
// multiplier
let mul = 1;
for (let i = 0; i < 30; i++) {
// variable to store number of
// sub-arrays with odd number of elements
// with ith bits starting from the first
// element to the end of the array
let c_odd = 0;
// variable to check the status
// of the odd-even count while
// calculating c_odd
let odd = 0;
// loop to calculate initial
// value of c_odd
for (let j = 0; j < n; j++) {
if ((arr[j] & (1 << i)) > 0)
odd = (!odd);
if (odd)
c_odd++;
}
// loop to iterate through
// all the elements of the
// array and update sum
for (let j = 0; j < n; j++) {
sum += (mul * c_odd);
if ((arr[j] & (1 << i)) > 0)
c_odd = (n - j - c_odd);
}
// updating the multiplier
mul *= 2;
}
// returning the sum
return sum;
}
// Driver Code
let arr = [ 3, 8, 13 ];
let n = arr.length;
document.write(findXorSum(arr, n));
</script>
46
Complejidad de tiempo : O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA