Encuentre la suma XOR de Bitwise AND de todos los pares de dos arrays dadas

Dadas dos arrays A y B de tamaños N y M respectivamente, la tarea es calcular la suma XOR de AND bit a bit de todos los pares de A y B

Ejemplos:

Entrada: A={3, 5}, B={2, 3}, N=2, M=2
Salida:
0
Explicación:
La respuesta es (3&2)^(3&3)^(5&2)^(5&3)=1 ^3^0^2=0.

Entrada: A={1, 2, 3}, B={5, 6}, N=3, M=2
Salida:
0

Enfoque ingenuo: el enfoque ingenuo sería usar bucles anidados para calcular los AND bit a bit de todos los pares y luego encontrar su suma XOR . Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable ans a -1 , que almacenará esa respuesta final.
2. Atraviese la array A y haga lo siguiente:
   1. Para cada elemento actual, recorra la array B y haga lo siguiente:
      1. Si ans es igual a -1 , almacene el AND bit a bit de los elementos en ans.
      2. De lo contrario, almacene el XOR bit a bit de ans y el AND bit a bit de los elementos en ans .
3. Regresar respuesta

A continuación se muestra la implementación del enfoque anterior:

// C++ algorithm for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the XOR sum of all ANDS of all
// pairs on A[] and B[]
int XorSum(int A[], int B[], int N, int M)
{
    // variable to store anshu
    int ans = -1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            // when there has been no
            // AND of pairs before this
            if (ans == -1)
                ans = (A[i] & B[j]);
            else
                ans ^= (A[i] & B[j]);
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    // Input
    int A[] = { 3, 5 };
    int B[] = { 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
 
    // Function call
    cout << XorSum(A, B, N, M) << endl;
}

// Java program for the above approach
import java.io.*;
class GFG
{
   
  // Function to calculate the XOR sum of all ANDS of all
// pairs on A[] and B[]
public static int XorSum(int A[], int B[], int N, int M)
{
   
    // variable to store anshu
    int ans = -1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
           
            // when there has been no
            // AND of pairs before this
            if (ans == -1)
                ans = (A[i] & B[j]);
            else
                ans ^= (A[i] & B[j]);
        }
    }
    return ans;
}
 
// Driver code
    public static void main (String[] args)
    {
       
         // Input
    int A[] = { 3, 5 };
    int B[] = { 2, 3 };
    int N = A.length;
    int M =B.length;
 
    // Function call
    System.out.println(XorSum(A, B, N, M));
       
    }
}
 
// This code is contributed by Potta Lokesh

# Python3 algorithm for the above approach
 
# Function to calculate the XOR sum of all ANDS of all
# pairs on A and B
def XorSum(A, B, N, M):
   
    # variable to store anshu
    ans = -1
    for i in range(N):
        for j in range(M):
           
            # when there has been no
            # AND of pairs before this
            if (ans == -1):
                ans = (A[i] & B[j])
            else:
                ans ^= (A[i] & B[j])
 
    return ans
   
# Driver code
if __name__ == '__main__':
   
    # Input
    A = [3, 5]
    B = [2, 3]
 
    N = len(A)
    M = len(B)
 
    # Function call
    print (XorSum(A, B, N, M))
 
# This code is contributed by mohit kumar 29.

// C# algorithm for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to calculate the XOR sum of all ANDS of all
// pairs on A[] and B[]
static int XorSum(int []A, int []B, int N, int M)
{
   
    // variable to store anshu
    int ans = -1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
           
            // when there has been no
            // AND of pairs before this
            if (ans == -1)
                ans = (A[i] & B[j]);
            else
                ans ^= (A[i] & B[j]);
        }
    }
    return ans;
}
 
// Driver code
public static void Main()
{
    // Input]
    int []A = {3, 5};
    int []B = {2, 3};
    int N = A.Length;
    int M = B.Length;
 
    // Function call
    Console.Write(XorSum(A, B, N, M));
}
}
 
// This code is contributed by SURENDER_GANGWAR.

<script>
// JavaScript program for the above approach
 
        // Function to calculate the XOR sum of all ANDS of all
        // pairs on A[] and B[]
        function XorSum(A, B, N, M)
        {
         
            // variable to store anshu
            let ans = -1;
            for (let i = 0; i < N; i++)
            {
                for (let j = 0; j < M; j++)
                {
                 
                    // when there has been no
                    // AND of pairs before this
                    if (ans == -1)
                        ans = (A[i] & B[j]);
                    else
                        ans ^= (A[i] & B[j]);
                }
            }
            return ans;
        }
 
        // Driver code
 
        // Input
        let A = [3, 5];
        let B = [2, 3];
        let N = A.length;
        let M = B.length;
 
        // Function call
        document.write(XorSum(A, B, N, M));
 
  // This code is contributed by Potta Lokesh
    </script>

0

Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)

Enfoque eficiente:

Observación: La propiedad distributiva de XOR sobre AND puede usarse para resolver el problema. 

sea ​​A[] = [a, b, c] 
sea B[] = [d, e] 
Resultado: 
(a & d) ^ (a & e) ^ (b & d) ^ (b & e) ^ (c & d) ^ (c & e) 
Aplicando la propiedad distributiva, 
[(a ^ b ^ c) & d] ^ [(a ^ b ^ e) & e] 
(a ^ b ^ c) & (d ^ e) 
 

Siga los pasos a continuación para resolver el problema: 

• Inicialice dos variables ans1 y ans2 a 0 , que almacenarán las sumas XOR bit a bit de la primera array y la segunda array respectivamente.
• Traverse A y para cada elemento actual:
  • Almacene el XOR bit a bit de ans1 y el elemento actual en ans1 .
• Traverse B y para cada elemento actual:
  • Almacene el XOR bit a bit de ans2 y el elemento actual en ans2 .
• Devuelve ans1&ans2.

A continuación se muestra la implementación del enfoque anterior: 

// C++ algorithm for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the XOR sum of all ANDS of all
// pairs on A[] and B[]
int XorSum(int A[], int B[], int N, int M)
{
    // variable to store xor sums
    // of first array and second
    // array respectively.
    int ans1 = 0, ans2 = 0;
    // Xor sum of first array
    for (int i = 0; i < N; i++)
        ans1 = ans1 ^ A[i];
    // Xor sum of second array
    for (int i = 0; i < M; i++)
        ans2 = ans2 ^ B[i];
    // required answer
    return (ans1 & ans2);
}
// Driver code
int main()
{
    // Input
    int A[] = { 3, 5 };
    int B[] = { 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
 
    // Function call
    cout << XorSum(A, B, N, M) << endl;
}

// Java algorithm for the above approach
import java.io.*;
 
class GFG{
 
// Function to calculate the XOR sum of
// all ANDS of all pairs on A[] and B[]
static int XorSum(int A[], int B[], int N, int M)
{
     
    // Variable to store xor sums
    // of first array and second
    // array respectively.
    int ans1 = 0, ans2 = 0;
     
    // Xor sum of first array
    for(int i = 0; i < N; i++)
        ans1 = ans1 ^ A[i];
         
    // Xor sum of second array
    for(int i = 0; i < M; i++)
        ans2 = ans2 ^ B[i];
         
    // Required answer
    return (ans1 & ans2);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Input
    int A[] = { 3, 5 };
    int B[] = { 2, 3 };
    int N = A.length;
    int M = B.length;
 
    // Function call
    System.out.print(XorSum(A, B, N, M));
}
}
 
// This code is contributed by subham348

# python 3 algorithm for the above approach
 
# Function to calculate the XOR sum of all ANDS of all
# pairs on A[] and B[]
def XorSum(A, B, N, M):
   
    # variable to store xor sums
    # of first array and second
    # array respectively.
    ans1 = 0
    ans2 = 0
     
    # Xor sum of first array
    for i in range(N):
        ans1 = ans1 ^ A[i]
         
    # Xor sum of second array
    for i in range(M):
        ans2 = ans2 ^ B[i]
         
    # required answer
    return (ans1 & ans2)
 
# Driver code
if __name__ == '__main__':
   
    # Input
    A = [3, 5]
    B = [2, 3]
    N = len(A)
    M = len(B)
 
    # Function call
    print(XorSum(A, B, N, M))
     
    # This code is contributed by bgangwar59.

// C# program for the above approach
 
using System;
 
class GFG {
 
// Function to calculate the XOR sum of
// all ANDS of all pairs on A[] and B[]
static int XorSum(int[] A, int[] B, int N, int M)
{
     
    // Variable to store xor sums
    // of first array and second
    // array respectively.
    int ans1 = 0, ans2 = 0;
     
    // Xor sum of first array
    for(int i = 0; i < N; i++)
        ans1 = ans1 ^ A[i];
         
    // Xor sum of second array
    for(int i = 0; i < M; i++)
        ans2 = ans2 ^ B[i];
         
    // Required answer
    return (ans1 & ans2);
}
 
  // Driver code
  public static void Main (String[] args)
  {
 
    // Input
    int[] A = { 3, 5 };
    int[] B = { 2, 3 };
    int N = A.Length;
    int M = B.Length;
 
    // Function call
    Console.Write(XorSum(A, B, N, M));
  }
}
 
// This code is contributed by code_hunt.

<script>
 
// JavaScript algorithm for the above approach
 
// Function to calculate the XOR sum of all ANDS of all
// pairs on A[] and B[]
function XorSum(A, B, N, M)
{
    // variable to store xor sums
    // of first array and second
    // array respectively.
    let ans1 = 0, ans2 = 0;
    // Xor sum of first array
    for (let i = 0; i < N; i++)
        ans1 = ans1 ^ A[i];
    // Xor sum of second array
    for (let i = 0; i < M; i++)
        ans2 = ans2 ^ B[i];
    // required answer
    return (ans1 & ans2);
}
// Driver code
    // Input
    let A = [ 3, 5 ];
    let B = [ 2, 3 ];
    let N = A.length;
    let M = B.length;
 
    // Function call
    document.write(XorSum(A, B, N, M));
 
</script>

0

Complejidad temporal: O(N)
Espacio auxiliar: O(1)