XOR de todas las posibles sumas por pares de dos arrays dadas

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:
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 = 2

Entrada: 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)

Publicación traducida automáticamente

Artículo escrito por __mahakal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *