Dada una array arr[] de longitud N , la tarea es encontrar el XOR de la suma por pares de todos los posibles pares desordenados de la array. La suma de pares desordenados se define de la siguiente manera:
XOR of pairwise sum = (A[0] + A[1]) ^
(A[0] + A[2]) ^ ...(A[0] + A[N]) ^
(A[1] + A[2]) ^ ...(A[1] + A[N]) ^
.......
(A[N-1] + A[N])
Notice that after including A[0] and A[1]
as pairs, then A[1] and A[0] are not included.
Ejemplos:
Entrada: arr[] = {1, 2}
Salida: 3
Explicación:
Solo hay un par desordenado. Es decir (1, 2)
Entrada: arr[] = {1, 2, 3}
Salida: 2
Explicación:
Pares desordenados de números –
{(1, 2), (1, 3), (2, 3)}
XOR de suma por pares desordenada –
=> (1 + 2) ^ (1 + 3) ^ (2 + 3)
=> 3 ^ 4 ^ 5
=> 2
Enfoque ingenuo: la idea es encontrar todos los pares desordenados posibles con la ayuda de los dos bucles y encontrar el XOR de estos pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find XOR of
// pairwise sum of every unordered
// pairs in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find XOR of pairwise
// sum of every unordered pairs
int xorOfSum(int a[], int n)
{
int answer = 0;
// Loop to choose every possible
// pairs in the array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
answer ^= (a[i] + a[j]);
}
return answer;
}
// Driver Code
int main()
{
int n = 3;
int A[n] = { 1, 2, 3 };
cout << xorOfSum(A, n);
return 0;
}
Java
// Java implementation to find XOR of
// pairwise sum of every unordered
// pairs in an array
class GFG{
// Function to find XOR of pairwise
// sum of every unordered pairs
static int xorOfSum(int a[], int n)
{
int answer = 0;
// Loop to choose every possible
// pairs in the array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
answer ^= (a[i] + a[j]);
}
return answer;
}
// Driver Code
public static void main(String[] args)
{
int n = 3;
int A[] = { 1, 2, 3 };
System.out.print(xorOfSum(A, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to find XOR of # pairwise sum of every unordered # pairs in an array # Function to find XOR of pairwise # sum of every unordered pairs def xorOfSum(a, n): answer = 0 # Loop to choose every possible # pairs in the array for i in range(n): for j in range(i + 1, n): answer ^= (a[i] + a[j]) return answer # Driver Code if __name__ == '__main__': n = 3 A=[1, 2, 3] print(xorOfSum(A, n)) # This code is contributed by mohit kumar 29
C#
// C# implementation to find XOR of
// pairwise sum of every unordered
// pairs in an array
using System;
using System.Collections.Generic;
class GFG{
// Function to find XOR of pairwise
// sum of every unordered pairs
static int xorOfSum(int []a, int n)
{
int answer = 0;
// Loop to choose every possible
// pairs in the array
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++)
answer ^= (a[i] + a[j]);
}
return answer;
}
// Driver Code
public static void Main(String[] args)
{
int n = 3;
int []A = { 1, 2, 3 };
Console.Write(xorOfSum(A, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation to find XOR of
// pairwise sum of every unordered
// pairs in an array
// Function to find XOR of pairwise
// sum of every unordered pairs
function xorOfSum(a, n)
{
let answer = 0;
// Loop to choose every possible
// pairs in the array
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++)
answer ^= (a[i] + a[j]);
}
return answer;
}
// Driver Code
let n = 3;
let A = [ 1, 2, 3 ];
document.write(xorOfSum(A, n));
// This code is contributed by Surbhi Tyagi
</script>
Producción:
2
Enfoque eficiente:
- Para obtener el k -ésimo bit del valor xor final, vemos en todas las sumas de pares, si el k -ésimo bit de ellos está establecido o no. Si hay incluso un número de pares que tienen el K -ésimo bit establecido, entonces para el K -ésimo bit, su xor es cero más uno.
- Para encontrar el recuento de sumas de pares que tienen establecido el bit K , observamos que podemos modificar todos los elementos de la array en 2 (K+1) . Esto se debe a que X e Y pertenecen a la array de entrada y Sum = X + Y. Entonces X + Y puede sumar para tener su K -ésimo bit establecido , lo que significa Suma >= 2 K. También se puede observar que pueden tener un remanente de la suma que hace que los números en el rango [2 (K+1) , 2 (K+1) + 2 K ) no tengan establecido su K -ésimo bit. Así que solo nos preocupamos por el K -ésimo y (K+1) -ésimo bit de todos los números para comprobar el XOR del K -ésimo bit.
- Después de realizar la operación de modulación, para que la suma tenga k-ésimo bit establecido, su valor estará en el rango – [2 K , 2 (K+1) ] U [2 (K+1) + 2 K , Max-Value-Sum -Puede tomar ].
- Para encontrar los números en dicho rango, cree otra array B que contenga elementos de array modificados de arr[] y ordénelos. Entonces Sum puede asumirse como Sum = B i + B j . Finalmente, encuentre el límite máximo de j usando la búsqueda binaria ( inferior_límite integrado en C++). Arregle i y, dado que la array está ordenada, encuentre el último j que satisfaga la condición dada y todos los números en el rango de índices se pueden agregar al conteo para verificar el xor.
Espacio auxiliar: O(1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find XOR of
// pairwise sum of every unordered
// pairs in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find XOR of pairwise
// sum of every unordered pairs
int xorOfSum(int a[], int n)
{
int i, j, k;
// Sort the array
sort(a, a + n);
int ans = 0;
// Array elements are not greater
// than 1e7 so 27 bits are suffice
for (k = 0; k < 27; ++k) {
// Modded elements of array
vector<int> b(n);
// Loop to find the modded
// elements of array
for (i = 0; i < n; i++)
b[i] = a[i] % (1 << (k + 1));
// Sort the modded array
sort(b.begin(), b.end());
int cnt = 0;
for (i = 0; i < n; i++) {
// finding the bound for j
// for given i using binary search
int l = lower_bound(b.begin() +
i + 1, b.end(),
(1 << k) - b[i]) - b.begin();
int r = lower_bound(b.begin() +
i + 1, b.end(), (1 << (k + 1)) -
b[i]) - b.begin();
// All the numbers in the range
// of indices can be added to the
// count to check the xor.
cnt += r - l;
l = lower_bound(b.begin() + i + 1,
b.end(), (1 << (k + 1)) +
(1 << k) - b[i]) - b.begin();
cnt += n - l;
}
// Remainder of cnt * kth power
// of 2 added to the xor value
ans += (cnt % 2) * 1LL * (1 << k);
}
return ans;
}
// Driver Code
int main()
{
int n = 3;
int A[n] = { 1, 2, 3 };
cout << xorOfSum(A, n);
return 0;
}
Python3
# Python3 implementation to find XOR of # pairwise sum of every unordered # pairs in an array # Function to find the lower_bound of an array # ie, the leftmost element that is greater than # or equal to the given element def lower_bound(arr, startIndex, element): n = len(arr) for i in range(startIndex, n): if (arr[i] >= element): return i return n # Function to find XOR of pairwise # sum of every unordered pairs def xorOfSum(a, n): # Sort the array a.sort() ans = 0 # Array elements are not greater # than 1e7 so 27 bits are suffice for k in range(27): # Modded elements of array b = [0 for _ in range(n)] # Loop to find the modded # elements of array for i in range(n): b[i] = a[i] % (1 << (k + 1)) # Sort the modded array b.sort() cnt = 0 for i in range(n): # finding the bound for j # for given i using binary search l = lower_bound(b, i + 1, (1 << k) - b[i]) r = lower_bound(b, i + 1, (1 << (k + 1)) - b[i]) # All the numbers in the range # of indices can be added to the # count to check the xor. cnt += r - l l = lower_bound(b, i + 1, (1 << (k + 1)) + (1 << k) - b[i]) cnt += n - l # Remainder of cnt * kth power # of 2 added to the xor value ans += (cnt % 2) * (1 << k) return ans # Driver Code n = 3 A = [1, 2, 3] # Function call print(xorOfSum(A, n)) # This code is contributed by phasing17
Javascript
// JavaScript implementation to find XOR of
// pairwise sum of every unordered
// pairs in an array
// Function to find the lower_bound of an array
// ie, the leftmost element that is greater than
// or equal to the given element
function lower_bound(array, startIndex, element)
{
var n = array.length;
for (var i = startIndex; i < n; i++)
{
if (array[i] >= element)
return i;
}
return n;
}
// Function to find XOR of pairwise
// sum of every unordered pairs
function xorOfSum(a, n)
{
var i;
var j;
var k;
// Sort the array
a.sort();
var ans = 0;
// Array elements are not greater
// than 1e7 so 27 bits are suffice
for (k = 0; k < 27; k++) {
// Modded elements of array
b = new Array(n);
// Loop to find the modded
// elements of array
for (i = 0; i < n; i++)
b[i] = a[i] % (1 << (k + 1));
// Sort the modded array
b.sort();
var cnt = 0;
for (i = 0; i < n; i++)
{
// finding the bound for j
// for given i using binary search
var l = lower_bound(b, i + 1, (1 << k) - b[i]);
var r = lower_bound(b,i + 1, (1 << (k + 1)) - b[i]);
// All the numbers in the range
// of indices can be added to the
// count to check the xor.
cnt += r - l;
l = lower_bound(b, i + 1, (1 << (k + 1)) +
(1 << k) - b[i]);
cnt += n - l;
}
// Remainder of cnt * kth power
// of 2 added to the xor value
ans += (cnt % 2) * (1 << k);
}
return ans;
}
// Driver Code
var n = 3;
var A = [ 1, 2, 3 ];
// Function call
console.log(xorOfSum(A, n));
// this code is contributed by phasing17
Producción:
2
Análisis de rendimiento:
- Complejidad del tiempo: O(N * log(max(A))*log(N)
- Espacio Auxiliar: O(N)
El bucle más externo se ejecuta por log(max(A)) veces y para cada bucle creamos y ordenamos la array b, que consta de N elementos, por lo que la complejidad es O(N*log(N)*log(max(A)))