Dada una array arr[] de tamaño N y una array Q[] , la tarea es calcular la suma de Bitwise XOR de todos los elementos de la array arr[] con cada elemento de la array q[] .
Ejemplos:
Entrada: arr[ ] = {5, 2, 3}, Q[ ] = {3, 8, 7}
Salida: 7 34 11
Explicación:
Para Q[0] ( = 3): Suma = 5 ^ 3 + 2 ^ 3 + 3 ^ 3 = 7.
Para Q[1] ( = 8): Suma = 5 ^ 8 + 2 ^ 8 + 3 ^ 8 = 34.
Para Q[2] ( = 7): Suma = 5 ^ 7 + 2^7 + 3^7 = 11.Entrada: arr[ ] = {2, 3, 4}, Q[ ] = {1, 2}
Salida: 10 7
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array Q[] y, para cada elemento de la array, calcular la suma de su XOR bit a bit con todos los elementos de la array arr[] .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Inicialice una array count[] , de tamaño 32 . para almacenar el recuento de bits establecidos en cada posición de los elementos de la array arr[].
- Recorre la array arr[] .
- Actualice el recuento de arrays [] en consecuencia. En una representación binaria de 32 bits , si se establece el i -ésimo bit, aumente el recuento de bits establecidos en esa posición.
- Recorra la array Q[] y para cada elemento de la array, realice las siguientes operaciones:
- Inicialice las variables, digamos sum = 0, para almacenar la suma requerida de Bitwise XOR.
- Iterar sobre cada posición de bit del elemento actual.
- Si el bit actual está configurado, agregue el recuento de elementos con i -ésimo bit no configurado * 2 i para sumar .
- De lo contrario, agregue count[i] * 2 i .
- Finalmente, imprima el valor de sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate sum of Bitwise
// XOR of elements of arr[] with k
int xorSumOfArray(int arr[], int n, int k, int count[])
{
// Initialize sum to be zero
int sum = 0;
int p = 1;
// Iterate over each set bit
for (int i = 0; i < 31; i++) {
// Stores contribution of
// i-th bet to the sum
int val = 0;
// If the i-th bit is set
if ((k & (1 << i)) != 0) {
// Stores count of elements
// whose i-th bit is not set
int not_set = n - count[i];
// Update value
val = ((not_set)*p);
}
else {
// Update value
val = (count[i] * p);
}
// Add value to sum
sum += val;
// Move to the next
// power of two
p = (p * 2);
}
return sum;
}
void sumOfXors(int arr[], int n, int queries[], int q)
{
// Stores the count of elements
// whose i-th bit is set
int count[32];
// Initialize count to 0
// for all positions
memset(count, 0, sizeof(count));
// Traverse the array
for (int i = 0; i < n; i++) {
// Iterate over each bit
for (int j = 0; j < 31; j++) {
// If the i-th bit is set
if (arr[i] & (1 << j))
// Increase count
count[j]++;
}
}
for (int i = 0; i < q; i++) {
int k = queries[i];
cout << xorSumOfArray(arr, n, k, count) << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 5, 2, 3 };
int queries[] = { 3, 8, 7 };
int n = sizeof(arr) / sizeof(int);
int q = sizeof(queries) / sizeof(int);
sumOfXors(arr, n, queries, q);
return 0;
}
Java
// Java Program for the above approach
import java.util.Arrays;
class GFG{
// Function to calculate sum of Bitwise
// XOR of elements of arr[] with k
static int xorSumOfArray(int arr[], int n,
int k, int count[])
{
// Initialize sum to be zero
int sum = 0;
int p = 1;
// Iterate over each set bit
for(int i = 0; i < 31; i++)
{
// Stores contribution of
// i-th bet to the sum
int val = 0;
// If the i-th bit is set
if ((k & (1 << i)) != 0)
{
// Stores count of elements
// whose i-th bit is not set
int not_set = n - count[i];
// Update value
val = ((not_set)*p);
}
else
{
// Update value
val = (count[i] * p);
}
// Add value to sum
sum += val;
// Move to the next
// power of two
p = (p * 2);
}
return sum;
}
static void sumOfXors(int arr[], int n,
int queries[], int q)
{
// Stores the count of elements
// whose i-th bit is set
int []count = new int[32];
// Initialize count to 0
// for all positions
Arrays.fill(count,0);
// Traverse the array
for(int i = 0; i < n; i++)
{
// Iterate over each bit
for(int j = 0; j < 31; j++)
{
// If the i-th bit is set
if ((arr[i] & (1 << j)) != 0)
// Increase count
count[j]++;
}
}
for(int i = 0; i < q; i++)
{
int k = queries[i];
System.out.print(
xorSumOfArray(arr, n, k, count) + " ");
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 5, 2, 3 };
int queries[] = { 3, 8, 7 };
int n = arr.length;
int q = queries.length;
sumOfXors(arr, n, queries, q);
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 Program for the above approach # Function to calculate sum of Bitwise # XOR of elements of arr[] with k def xorSumOfArray(arr, n, k, count): # Initialize sum to be zero sum = 0 p = 1 # Iterate over each set bit for i in range(31): # Stores contribution of # i-th bet to the sum val = 0 # If the i-th bit is set if ((k & (1 << i)) != 0): # Stores count of elements # whose i-th bit is not set not_set = n - count[i] # Update value val = ((not_set)*p) else: # Update value val = (count[i] * p) # Add value to sum sum += val # Move to the next # power of two p = (p * 2) return sum def sumOfXors(arr, n, queries, q): # Stores the count of elements # whose i-th bit is set count = [0 for i in range(32)] # Traverse the array for i in range(n): # Iterate over each bit for j in range(31): # If the i-th bit is set if (arr[i] & (1 << j)): # Increase count count[j] += 1 for i in range(q): k = queries[i] print(xorSumOfArray(arr, n, k, count), end = " ") # Driver Code if __name__ == '__main__': arr = [ 5, 2, 3 ] queries = [ 3, 8, 7 ] n = len(arr) q = len(queries) sumOfXors(arr, n, queries, q) # This code is contributed by SURENDRA_GANGWAR
C#
// C# Program for the above approach
using System;
public class GFG{
// Function to calculate sum of Bitwise
// XOR of elements of arr[] with k
static int xorSumOfArray(int []arr, int n, int k, int []count)
{
// Initialize sum to be zero
int sum = 0;
int p = 1;
// Iterate over each set bit
for (int i = 0; i < 31; i++) {
// Stores contribution of
// i-th bet to the sum
int val = 0;
// If the i-th bit is set
if ((k & (1 << i)) != 0) {
// Stores count of elements
// whose i-th bit is not set
int not_set = n - count[i];
// Update value
val = ((not_set)*p);
}
else {
// Update value
val = (count[i] * p);
}
// Add value to sum
sum += val;
// Move to the next
// power of two
p = (p * 2);
}
return sum;
}
static void sumOfXors(int []arr, int n, int []queries, int q)
{
// Stores the count of elements
// whose i-th bit is set
int []count = new int[32];
// Initialize count to 0
// for all positions
for(int i = 0; i < 32; i++)
count[i] = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Iterate over each bit
for (int j = 0; j < 31; j++) {
// If the i-th bit is set
if ((arr[i] & (1 << j)) != 0)
// Increase count
count[j]++;
}
}
for (int i = 0; i < q; i++) {
int k = queries[i];
Console.Write(xorSumOfArray(arr, n, k, count) + " ");
}
}
// Driver Code
static public void Main ()
{
int []arr = { 5, 2, 3 };
int []queries = { 3, 8, 7 };
int n = arr.Length;
int q = queries.Length;
sumOfXors(arr, n, queries, q);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to calculate sum of Bitwise
// XOR of elements of arr[] with k
function xorSumOfArray(arr, n, k, count)
{
// Initialize sum to be zero
var sum = 0;
var p = 1;
// Iterate over each set bit
for(var i = 0; i < 31; i++)
{
// Stores contribution of
// i-th bet to the sum
var val = 0;
// If the i-th bit is set
if ((k & (1 << i)) != 0)
{
// Stores count of elements
// whose i-th bit is not set
var not_set = n - count[i];
// Update value
val = ((not_set)*p);
}
else
{
// Update value
val = (count[i] * p);
}
// Add value to sum
sum += val;
// Move to the next
// power of two
p = (p * 2);
}
return sum;
}
function sumOfXors(arr, n, queries, q)
{
// Stores the count of elements
// whose i-th bit is set
var count = new Array(32);
// Initialize count to 0
// for all positions
count.fill(0);
// Traverse the array
for(var i = 0; i < n; i++)
{
// Iterate over each bit
for(var j = 0; j < 31; j++)
{
// If the i-th bit is set
if (arr[i] & (1 << j))
// Increase count
count[j]++;
}
}
for(var i = 0; i < q; i++)
{
var k = queries[i];
document.write(xorSumOfArray(
arr, n, k, count) + " ");
}
}
// Driver code
var arr = [ 5, 2, 3 ];
var queries = [ 3, 8, 7 ];
var n = arr.length;
var q = queries.length;
sumOfXors(arr, n, queries, q);
// This code is contributed by SoumikMondal
</script>
Producción:
7 34 11
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por elitecoder y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA