Dada una array arr[] de longitud N , la tarea de cada elemento de la array es imprimir la suma de su Bitwise XOR con todos los demás elementos de la array.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 5 4 3
Explicación:
Para arr[0]: arr[0] ^ arr[0] + arr[0] ^ arr[1] + arr[0] ^ arr[2] = 1^1 + 1^2 + 1^3 = 0 + 3 + 2 = 5
Para arr[1]: arr[1] ^ arr[0] + arr[1] ^ arr[1] + arr[1] ^ arr[2] = 2^1 + 2^2 + 2^3 = 3 + 0 + 1 = 4
Para arr[2]: arr[2] ^ arr[0] + arr[2] ^ array[1] + array[2] ^ array[2] = 3^1 + 3^2 + 3^3 = 2 + 2 + 0 = 3Entrada: arr[] ={2, 4, 8}
Salida: 16 18 22
Explicación:
Para arr[0]: arr[0] ^ arr[0] + arr[0] ^ arr[1] + arr[0] ^ arr[2] = 2^2 + 2^4 + 2^8 = 0 + 6 + 10 = 16.
Para arr[1]: arr[1] ^ arr[0] + arr[1] ^ arr[1 ] + arr[1] ^ arr[2] = 4^2 + 4^4 + 4^8 = 6 + 0 + 12 = 18
Para arr[2]: arr[2] ^ arr[0] + arr[2 ] ^ array[1] + array[2] ^ array[2] = 8^2 + 8^4 + 8^8 = 10 + 12 + 0 = 22
Enfoque ingenuo: la idea es recorrer la array y, para cada elemento de la array, recorrer la array y calcular la suma de su XOR bit a bit con todos los demás elementos de la array.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar la propiedad de Bitwise XOR que bits similares en xor dan 0 o 1 de lo contrario. Siga los pasos a continuación para resolver el problema:
- Calcule la frecuencia de los bits establecidos en la posición i donde 0 <= i <= 32 , en todos los elementos de la array en una array de frecuencia.
- Para cada elemento X , de la array, calcule la suma xor ejecutando un ciclo de i=0 a 32 y verifique si el i -ésimo bit de X está configurado.
- En caso afirmativo, agregue (N – frecuencia[i])*2 i a la suma xor porque el bit establecido de X en esta posición hará que todos los bits establecidos sean cero y todos los bits no establecidos sean 1 .
- De lo contrario, agregue frecuencia[i] * 2 i a la suma xor.
- Calcule la suma de todos los x o la suma de cada elemento de la array y regrese como la respuesta.
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 for each array
// element, sum of its Bitwise XOR with
// all other array elements
void XOR_for_every_i(int A[], int N)
{
// Declare an array of size 64
// to store count of each bit
int frequency_of_bits[32]{};
// Traversing the array
for (int i = 0; i < N; i++) {
int bit_position = 0;
int M = A[i];
while (M) {
// Check if bit is present of not
if (M & 1) {
frequency_of_bits[bit_position] += 1;
}
// Increase the bit position
bit_position += 1;
// Reduce the number to half
M >>= 1;
}
}
// Traverse the array
for (int i = 0; i < N; i++) {
int M = A[i];
// Stores the bit position
int value_at_that_bit = 1;
// Stores the sum of Bitwise XOR
int XOR_sum = 0;
for (int bit_position = 0;
bit_position < 32;
bit_position++) {
// Check if bit is present of not
if (M & 1) {
XOR_sum
+= (N
- frequency_of_bits[bit_position])
* value_at_that_bit;
}
else {
XOR_sum
+= (frequency_of_bits[bit_position])
* value_at_that_bit;
}
// Reduce the number to its half
M >>= 1;
value_at_that_bit <<= 1;
}
// Print the sum for A[i]
cout << XOR_sum << ' ';
}
return;
}
// Driver Code
int main()
{
// Given array
int A[] = { 1, 2, 3 };
// Given N
int N = sizeof(A) / sizeof(A[0]);
// Function Call
XOR_for_every_i(A, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to calculate for each array
// element, sum of its Bitwise XOR with
// all other array elements
static void XOR_for_every_i(int A[], int N)
{
// Declare an array of size 64
// to store count of each bit
int frequency_of_bits[] = new int[32];
// Traversing the array
for(int i = 0; i < N; i++)
{
int bit_position = 0;
int M = A[i];
while (M != 0)
{
// Check if bit is present of not
if ((M & 1) != 0)
{
frequency_of_bits[bit_position] += 1;
}
// Increase the bit position
bit_position += 1;
// Reduce the number to half
M >>= 1;
}
}
// Traverse the array
for(int i = 0; i < N; i++)
{
int M = A[i];
// Stores the bit position
int value_at_that_bit = 1;
// Stores the sum of Bitwise XOR
int XOR_sum = 0;
for(int bit_position = 0;
bit_position < 32;
bit_position++)
{
// Check if bit is present of not
if ((M & 1) != 0)
{
XOR_sum += (N -
frequency_of_bits[bit_position]) *
value_at_that_bit;
}
else
{
XOR_sum += (frequency_of_bits[bit_position]) *
value_at_that_bit;
}
// Reduce the number to its half
M >>= 1;
value_at_that_bit <<= 1;
}
// Print the sum for A[i]
System.out.print( XOR_sum + " ");
}
return;
}
// Driver code
public static void main(String[] args)
{
// Given array
int A[] = { 1, 2, 3 };
// Given N
int N = A.length;
// Function Call
XOR_for_every_i(A, N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to calculate for each array # element, sum of its Bitwise XOR with # all other array elements def XOR_for_every_i(A, N): # Declare an array of size 64 # to store count of each bit frequency_of_bits = [0] * 32 # Traversing the array for i in range(N): bit_position = 0 M = A[i] while (M): # Check if bit is present of not if (M & 1 != 0): frequency_of_bits[bit_position] += 1 # Increase the bit position bit_position += 1 # Reduce the number to half M >>= 1 # Traverse the array for i in range(N): M = A[i] # Stores the bit position value_at_that_bit = 1 # Stores the sum of Bitwise XOR XOR_sum = 0 for bit_position in range(32): # Check if bit is present of not if (M & 1 != 0): XOR_sum += ((N - frequency_of_bits[bit_position]) * value_at_that_bit) else: XOR_sum += ((frequency_of_bits[bit_position]) * value_at_that_bit) # Reduce the number to its half M >>= 1 value_at_that_bit <<= 1 # Print the sum for A[i] print(XOR_sum, end = " ") return # Driver Code # Given arr1[] A = [ 1, 2, 3 ] # Size of N N = len(A) # Function Call XOR_for_every_i(A, N) # This code is contributed by code_hunt
C#
// C# program for the above approach
using System;
class GFG
{
// Function to calculate for each array
// element, sum of its Bitwise XOR with
// all other array elements
static void XOR_for_every_i(int[] A, int N)
{
// Declare an array of size 64
// to store count of each bit
int[] frequency_of_bits = new int[32];
// Traversing the array
for(int i = 0; i < N; i++)
{
int bit_position = 0;
int M = A[i];
while (M != 0)
{
// Check if bit is present of not
if ((M & 1) != 0)
{
frequency_of_bits[bit_position] += 1;
}
// Increase the bit position
bit_position += 1;
// Reduce the number to half
M >>= 1;
}
}
// Traverse the array
for(int i = 0; i < N; i++)
{
int M = A[i];
// Stores the bit position
int value_at_that_bit = 1;
// Stores the sum of Bitwise XOR
int XOR_sum = 0;
for(int bit_position = 0;
bit_position < 32;
bit_position++)
{
// Check if bit is present of not
if ((M & 1) != 0)
{
XOR_sum += (N -
frequency_of_bits[bit_position]) *
value_at_that_bit;
}
else
{
XOR_sum += (frequency_of_bits[bit_position]) *
value_at_that_bit;
}
// Reduce the number to its half
M >>= 1;
value_at_that_bit <<= 1;
}
// Print the sum for A[i]
Console.Write( XOR_sum + " ");
}
return;
}
// Driver Code
public static void Main()
{
// Given array
int[] A = { 1, 2, 3 };
// Given N
int N = A.Length;
// Function Call
XOR_for_every_i(A, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate for each array
// element, sum of its Bitwise XOR with
// all other array elements
function XOR_for_every_i(A, N)
{
// Declare an array of size 64
// to store count of each bit
let frequency_of_bits = new Uint8Array(32);
// Traversing the array
for(let i = 0; i < N; i++)
{
let bit_position = 0;
let M = A[i];
while (M != 0)
{
// Check if bit is present of not
if ((M & 1) != 0)
{
frequency_of_bits[bit_position] += 1;
}
// Increase the bit position
bit_position += 1;
// Reduce the number to half
M >>= 1;
}
}
// Traverse the array
for(let i = 0; i < N; i++)
{
let M = A[i];
// Stores the bit position
let value_at_that_bit = 1;
// Stores the sum of Bitwise XOR
let XOR_sum = 0;
for(let bit_position = 0;
bit_position < 32;
bit_position++)
{
// Check if bit is present of not
if ((M & 1) != 0)
{
XOR_sum += (N -
frequency_of_bits[bit_position]) *
value_at_that_bit;
}
else
{
XOR_sum += (frequency_of_bits[bit_position]) *
value_at_that_bit;
}
// Reduce the number to its half
M >>= 1;
value_at_that_bit <<= 1;
}
// Print the sum for A[i]
document.write( XOR_sum + " ");
}
return;
}
// Driver code
// Given array
let A = [ 1, 2, 3 ];
// Given N
let N = A.length;
// Function Call
XOR_for_every_i(A, N);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
5 4 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)