Dadas dos arrays A[] y B[] de igual longitud, la tarea es encontrar el XOR bit a bit de la suma por pares de las dos arrays dadas.
Ejemplos:
Entrada: A[] = {1, 2}, B[] = {3, 4}
Salida: 2
Explicación:
La suma de todos los pares posibles es {4(1 + 3), 5(1 + 4), 5(2 + 3), 6(2 + 4)}
XOR de todas las sumas de pares = 4 ^ 5 ^ 5 ^ 6 = 2Entrada: A[] = {4, 6, 0, 0, 3, 3}, B[] = {0, 5, 6, 5, 0, 3}
Salida: 8
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles a partir de las dos arrays dadas y calcular sus respectivas sumas y actualizar XOR con la suma de los pares. Finalmente, imprime el XOR obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum of
// XOR of the sum of every pair
int XorSum(int A[], int B[], int N)
{
// Stores the XOR of sums
// of every pair
int ans = 0;
// Iterate to generate all possible pairs
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// Update XOR
ans = ans ^ (A[i] + B[j]);
}
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
int A[] = { 4, 6, 0, 0, 3, 3 };
int B[] = { 0, 5, 6, 5, 0, 3 };
int N = sizeof A / sizeof A[0];
cout << XorSum(A, B, N) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to calculate the sum of
// XOR of the sum of every pair
static int XorSum(int A[], int B[], int N)
{
// Stores the XOR of sums
// of every pair
int ans = 0;
// Iterate to generate all possible pairs
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
// Update XOR
ans = ans ^ (A[i] + B[j]);
}
}
// Return the answer
return ans;
}
// Driver Code
public static void main (String[] args)
{
int A[] = { 4, 6, 0, 0, 3, 3 };
int B[] = { 0, 5, 6, 5, 0, 3 };
int N = A.length;
System.out.println(XorSum(A, B, N));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to implement # the above approach # Function to calculate the sum of # XOR of the sum of every pair def XorSum(A, B, N): # Stores the XOR of sums # of every pair ans = 0 # Iterate to generate all # possible pairs for i in range(N): for j in range(N): # Update XOR ans = ans ^ (A[i] + B[j]) # Return the answer return ans # Driver Code if __name__ == "__main__": A = [ 4, 6, 0, 0, 3, 3 ] B = [ 0, 5, 6, 5, 0, 3 ] N = len(A) print (XorSum(A, B, N)) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate the sum of
// XOR of the sum of every pair
static int XorSum(int []A, int []B, int N)
{
// Stores the XOR of sums
// of every pair
int ans = 0;
// Iterate to generate all possible pairs
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
// Update XOR
ans = ans ^ (A[i] + B[j]);
}
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []A = {4, 6, 0, 0, 3, 3};
int []B = {0, 5, 6, 5, 0, 3};
int N = A.Length;
Console.WriteLine(XorSum(A, B, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to implement
// the above approach
// Function to calculate the sum of
// XOR of the sum of every pair
function XorSum(A , B , N) {
// Stores the XOR of sums
// of every pair
var ans = 0;
// Iterate to generate all possible pairs
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
// Update XOR
ans = ans ^ (A[i] + B[j]);
}
}
// Return the answer
return ans;
}
// Driver Code
var A = [ 4, 6, 0, 0, 3, 3 ];
var B = [ 0, 5, 6, 5, 0, 3 ];
var N = A.length;
document.write(XorSum(A, B, N));
// This code contributed by umadevi9616
</script>
Producción:
8
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la técnica de manipulación de bits . Siga los pasos a continuación para resolver el problema:
- Considerando solo el K -ésimo bit , la tarea es contar el número de pares ( i, j ) de modo que se establezca el K -ésimo bit de ( Ai + Bj) .
- Si este número es impar, agregue X = 2 k a la respuesta. Solo estamos interesados en los valores de (a i , b j ) en módulo 2X .
- Por lo tanto, reemplace a i con a i % (2X) y b j con b j % (2X) , y suponga que a i y b j < 2X .
- Hay dos casos en los que se establece el k -ésimo bit de (a i + b j) :
- x ≤ ai + bj < 2x
- 3x ≤ ai + bj < 4x
- Por lo tanto, ordene b[] en orden creciente. Para una i fija, el conjunto de j que satisface X ≤ (a i +b j ) < 2X forma un intervalo.
- Por lo tanto, cuente el número de dichos j mediante la búsqueda binaria . Del mismo modo, maneje el segundo caso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// XOR of the sum of every pair
int XorSum(int A[], int B[], int N)
{
// Stores the maximum bit
const int maxBit = 29;
int ans = 0;
// Look for all the k-th bit
for (int k = 0; k < maxBit; k++) {
// Stores the modulo of
// elements B[] with (2^(k+1))
int C[N];
for (int i = 0; i < N; i++) {
// Calculate modulo of
// array B[] with (2^(k+1))
C[i] = B[i] % (1 << (k + 1));
}
// Sort the array C[]
sort(C, C + N);
// Stores the total number
// whose k-th bit is set
long long count = 0;
long long l, r;
for (int i = 0; i < N; i++) {
// Calculate and store the modulo
// of array A[] with (2^(k+1))
int x = A[i] % (1 << (k + 1));
// Lower bound to count the number
// of elements having k-th bit in
// the range (2^k - x, 2* 2^(k) - x)
l = lower_bound(C,
C + N,
(1 << k) - x)
- C;
r = lower_bound(C,
C + N,
(1 << k) * 2 - x)
- C;
// Add total number i.e (r - l)
// whose k-th bit is one
count += (r - l);
// Lower bound to count the number
// of elements having k-th bit in
// range (3 * 2^k - x, 4*2^(k) - x)
l = lower_bound(C,
C + N,
(1 << k) * 3 - x)
- C;
r = lower_bound(C,
C + N,
(1 << k) * 4 - x)
- C;
count += (r - l);
}
// If count is even, Xor of
// k-th bit becomes zero, no
// need to add to the answer.
// If count is odd, only then,
// add to the final answer
if (count & 1)
ans += (1 << k);
}
// Return answer
return ans;
}
// Driver code
int main()
{
int A[] = { 4, 6, 0, 0, 3, 3 };
int B[] = { 0, 5, 6, 5, 0, 3 };
int N = sizeof A / sizeof A[0];
// Function call
cout << XorSum(A, B, N) << endl;
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Lower bound
static int lower_bound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to calculate the
// XOR of the sum of every pair
static int XorSum(int A[],
int B[], int N)
{
// Stores the maximum bit
final int maxBit = 29;
int ans = 0;
// Look for all the k-th bit
for (int k = 0; k < maxBit; k++)
{
// Stores the modulo of
// elements B[] with (2^(k+1))
int []C = new int[N];
for (int i = 0; i < N; i++)
{
// Calculate modulo of
// array B[] with (2^(k+1))
C[i] = B[i] % (1 << (k + 1));
}
// Sort the array C[]
Arrays.sort(C);
// Stores the total number
// whose k-th bit is set
long count = 0;
long l, r;
for (int i = 0; i < N; i++)
{
// Calculate and store the modulo
// of array A[] with (2^(k+1))
int x = A[i] % (1 << (k + 1));
// Lower bound to count
// the number of elements
// having k-th bit in
// the range (2^k - x,
// 2* 2^(k) - x)
l = lower_bound(C, 0, N,
(1 << k) - x);
r = lower_bound(C, 0, N,
(1 << k) *
2 - x);
// Add total number i.e
// (r - l) whose k-th bit is one
count += (r - l);
// Lower bound to count
// the number of elements
// having k-th bit in
// range (3 * 2^k - x,
// 4*2^(k) - x)
l = lower_bound(C, 0, N,
(1 << k) *
3 - x);
r = lower_bound(C, 0, N,
(1 << k) *
4 - x);
count += (r - l);
}
// If count is even, Xor of
// k-th bit becomes zero, no
// need to add to the answer.
// If count is odd, only then,
// add to the final answer
if ((count & 1) != 0)
ans += (1 << k);
}
// Return answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int A[] = {4, 6, 0, 0, 3, 3};
int B[] = {0, 5, 6, 5, 0, 3};
int N = A.length;
// Function call
System.out.print(XorSum(A, B,
N) + "\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach from bisect import bisect, bisect_left, bisect_right # Function to calculate the # XOR of the sum of every pair def XorSum(A, B, N): # Stores the maximum bit maxBit = 29 ans = 0 # Look for all the k-th bit for k in range(maxBit): # Stores the modulo of # elements B[] with (2^(k+1)) C = [0] * N for i in range(N): # Calculate modulo of # array B[] with (2^(k+1)) C[i] = B[i] % (1 << (k + 1)) # Sort the array C[] C = sorted(C) # Stores the total number # whose k-th bit is set count = 0 l, r = 0, 0 for i in range(N): # Calculate and store the modulo # of array A[] with (2^(k+1)) x = A[i] % (1 << (k + 1)) # Lower bound to count the number # of elements having k-th bit in # the range (2^k - x, 2* 2^(k) - x) l = bisect_left(C, (1 << k) - x) r = bisect_left(C, (1 << k) * 2 - x) # Add total number i.e (r - l) # whose k-th bit is one count += (r - l) # Lower bound to count the number # of elements having k-th bit in # range (3 * 2^k - x, 4*2^(k) - x) l = bisect_left(C, (1 << k) * 3 - x) r = bisect_left(C, (1 << k) * 4 - x) count += (r - l) # If count is even, Xor of # k-th bit becomes zero, no # need to add to the answer. # If count is odd, only then, # add to the final answer if (count & 1): ans += (1 << k) # Return answer return ans # Driver code if __name__ == '__main__': A = [ 4, 6, 0, 0, 3, 3 ] B = [ 0, 5, 6, 5, 0, 3 ] N = len(A) # Function call print(XorSum(A, B, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Lower bound
static int lower_bound(int[] a, int low,
int high, int element)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to calculate the
// XOR of the sum of every pair
static int XorSum(int[] A, int[] B, int N)
{
// Stores the maximum bit
int maxBit = 29;
int ans = 0;
// Look for all the k-th bit
for(int k = 0; k < maxBit; k++)
{
// Stores the modulo of
// elements B[] with (2^(k+1))
int[] C = new int[N];
for(int i = 0; i < N; i++)
{
// Calculate modulo of
// array B[] with (2^(k+1))
C[i] = B[i] % (1 << (k + 1));
}
// Sort the array C[]
Array.Sort(C);
// Stores the total number
// whose k-th bit is set
long count = 0;
long l, r;
for(int i = 0; i < N; i++)
{
// Calculate and store the modulo
// of array A[] with (2^(k+1))
int x = A[i] % (1 << (k + 1));
// Lower bound to count
// the number of elements
// having k-th bit in
// the range (2^k - x,
// 2* 2^(k) - x)
l = lower_bound(C, 0, N,
(1 << k) - x);
r = lower_bound(C, 0, N,
(1 << k) * 2 - x);
// Add total number i.e
// (r - l) whose k-th bit is one
count += (r - l);
// Lower bound to count
// the number of elements
// having k-th bit in
// range (3 * 2^k - x,
// 4*2^(k) - x)
l = lower_bound(C, 0, N,
(1 << k) * 3 - x);
r = lower_bound(C, 0, N,
(1 << k) * 4 - x);
count += (r - l);
}
// If count is even, Xor of
// k-th bit becomes zero, no
// need to add to the answer.
// If count is odd, only then,
// add to the final answer
if ((count & 1) != 0)
ans += (1 << k);
}
// Return answer
return ans;
}
// Driver code
public static void Main(string[] args)
{
int[] A = { 4, 6, 0, 0, 3, 3 };
int[] B = { 0, 5, 6, 5, 0, 3 };
int N = A.Length;
// Function call
Console.Write(XorSum(A, B, N) + "\n");
}
}
// This code is contributed by grand_master
Javascript
<script>
// Javascript Program to implement
// the above approach
// Lower bound
function lower_bound(a,low,high,element)
{
while(low < high)
{
let middle = low + Math.floor((high - low) / 2);
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to calculate the
// XOR of the sum of every pair
function XorSum(A,B,N)
{
// Stores the maximum bit
let maxBit = 29;
let ans = 0;
// Look for all the k-th bit
for (let k = 0; k < maxBit; k++)
{
// Stores the modulo of
// elements B[] with (2^(k+1))
let C = new Array(N);
for (let i = 0; i < N; i++)
{
// Calculate modulo of
// array B[] with (2^(k+1))
C[i] = B[i] % (1 << (k + 1));
}
// Sort the array C[]
C.sort(function(x,y){return x-y;});
// Stores the total number
// whose k-th bit is set
let count = 0;
let l, r;
for (let i = 0; i < N; i++)
{
// Calculate and store the modulo
// of array A[] with (2^(k+1))
let x = A[i] % (1 << (k + 1));
// Lower bound to count
// the number of elements
// having k-th bit in
// the range (2^k - x,
// 2* 2^(k) - x)
l = lower_bound(C, 0, N,
(1 << k) - x);
r = lower_bound(C, 0, N,
(1 << k) *
2 - x);
// Add total number i.e
// (r - l) whose k-th bit is one
count += (r - l);
// Lower bound to count
// the number of elements
// having k-th bit in
// range (3 * 2^k - x,
// 4*2^(k) - x)
l = lower_bound(C, 0, N,
(1 << k) *
3 - x);
r = lower_bound(C, 0, N,
(1 << k) *
4 - x);
count += (r - l);
}
// If count is even, Xor of
// k-th bit becomes zero, no
// need to add to the answer.
// If count is odd, only then,
// add to the final answer
if ((count & 1) != 0)
ans += (1 << k);
}
// Return answer
return ans;
}
// Driver code
let A=[4, 6, 0, 0, 3, 3];
let B=[0, 5, 6, 5, 0, 3];
let N = A.length;
// Function call
document.write(XorSum(A, B,
N) + "\n");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
8
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)