Bitwise XOR de los mismos elementos de array indexados después de reorganizar una array para hacer XOR de los mismos elementos indexados de dos arrays iguales

Dados dos arreglos A[] y B[] que consisten en N enteros positivos, la tarea es realizar el XOR bit a bit de los mismos elementos de arreglo indexados después de reorganizar el arreglo B[] de modo que el XOR bit a bit de los mismos elementos indexados de los arreglos A[ ] se vuelve igual.

Ejemplos:

Entrada: A[] = {1, 2, 3}, B[] = {4, 6, 7}
Salida: 5
Explicación:
A continuación se muestran los arreglos posibles:

Reorganice la array B[] a {4, 7, 6}. Ahora, el XOR bit a bit de los mismos elementos indexados son iguales, es decir, 1 ^ 4 = 5, 2 ^ 7 = 5, 3 ^ 6 = 5.

Después de los reordenamientos, Bitwise XOR requerido es 5.

Entrada: A[] = { 7, 8, 14 }, B[] = { 5, 12, 3 }
Salida: 11
Explicación:
A continuación se muestran los arreglos posibles:

Reorganice la array B[] a {12, 3, 5}. Ahora, el XOR bit a bit de los mismos elementos indexados son iguales, es decir, 7 ^ 12 = 11, 8 ^ 3 = 11, 14 ^ 5 = 11.

Después de los reordenamientos, Bitwise XOR requerido es 11.

Enfoque ingenuo: el problema dado se puede resolver en función de la observación de que el recuento de reordenamientos puede ser como máximo N porque cualquier elemento en A[] solo se puede emparejar con otros N enteros en B[] . Entonces, hay N valores candidatos para X . Ahora, simplemente haga XOR a todos los candidatos con cada elemento en A[] y compruebe si B[] se puede organizar en ese orden.

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 find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
void findPossibleValues(int A[], int B[],
                        int n)
{
 
    // Sort the array B
    sort(B, B + n);
    int C[n];
 
    // Stores all the possible values
    // of the Bitwise XOR
    set<int> numbers;
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            C[j] = A[j] ^ candidate;
        }
 
        sort(C, C + n);
        bool flag = false;
 
        // Verify if the considered value
        // satisfies the condition or not
        for (int j = 0; j < n; j++)
            if (C[j] != B[j])
                flag = true;
 
        // Insert the possible Bitwise
        // XOR value
        if (!flag)
            numbers.insert(candidate);
    }
 
    // Print all the values obtained
    for (auto x : numbers) {
        cout << x << " ";
    }
}
 
// Driver Code
int main()
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findPossibleValues(A, B, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int A[], int B[],
                        int n)
{
 
    // Sort the array B
    Arrays.sort(B);
    int []C = new int[n];
 
    // Stores all the possible values
    // of the Bitwise XOR
    HashSet<Integer> numbers = new HashSet<Integer>();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            C[j] = A[j] ^ candidate;
        }
 
        Arrays.sort(C);
        boolean flag = false;
 
        // Verify if the considered value
        // satisfies the condition or not
        for (int j = 0; j < n; j++)
            if (C[j] != B[j])
                flag = true;
 
        // Insert the possible Bitwise
        // XOR value
        if (!flag)
            numbers.add(candidate);
    }
 
    // Print all the values obtained
    for (int x : numbers) {
        System.out.print(x+ " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = A.length;
    findPossibleValues(A, B, N);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for the above approach
 
# Function to find all possible values
# of Bitwise XOR such after rearranging
# the array elements the Bitwise XOR
# value at corresponding indexes is same
def findPossibleValues(A, B, n):
   
  # Sort the array B
  B.sort();
  C = [0] * n;
 
  # Stores all the possible values
  # of the Bitwise XOR
  numbers = set();
 
  # Iterate over the range
  for i in range(n):
     
    # Possible value of K
    candidate = A[0] ^ B[i];
 
    # Array B for the considered
    # value of K
    for j in range(n):
      C[j] = A[j] ^ candidate;
     
 
    C.sort();
    flag = False;
 
    # Verify if the considered value
    # satisfies the condition or not
    for j in range(n):
        if (C[j] != B[j]):
             flag = True;
 
    # Insert the possible Bitwise
    # XOR value
    if (not flag):
        numbers.add(candidate);
   
 
  # Print all the values obtained
  for x in numbers:
    print(x, end = " ");
   
# Driver Code
A = [7, 8, 14];
B = [5, 12, 3];
N = len(A);
findPossibleValues(A, B, N);
 
# This code is contributed by gfgking.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int []A, int []B,
                        int n)
{
 
    // Sort the array B
    Array.Sort(B);
    int []C = new int[n];
 
    // Stores all the possible values
    // of the Bitwise XOR
    HashSet<int> numbers = new HashSet<int>();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            C[j] = A[j] ^ candidate;
        }
 
        Array.Sort(C);
        bool flag = false;
 
        // Verify if the considered value
        // satisfies the condition or not
        for (int j = 0; j < n; j++)
            if (C[j] != B[j])
                flag = true;
 
        // Insert the possible Bitwise
        // XOR value
        if (!flag)
            numbers.Add(candidate);
    }
 
    // Print all the values obtained
    foreach (int x in numbers) {
        Console.Write(x+ " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 7, 8, 14 };
    int []B = { 5, 12, 3 };
    int N = A.Length;
    findPossibleValues(A, B, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
function findPossibleValues(A, B, n) {
  // Sort the array B
  B.sort((a, b) => a - b);
  let C = new Array(n);
 
  // Stores all the possible values
  // of the Bitwise XOR
  let numbers = new Set();
 
  // Iterate over the range
  for (let i = 0; i < n; i++) {
    // Possible value of K
    let candidate = A[0] ^ B[i];
 
    // Array B for the considered
    // value of K
    for (let j = 0; j < n; j++) {
      C[j] = A[j] ^ candidate;
    }
 
    C.sort((a, b) => a - b);
    let flag = false;
 
    // Verify if the considered value
    // satisfies the condition or not
    for (let j = 0; j < n; j++) if (C[j] != B[j]) flag = true;
 
    // Insert the possible Bitwise
    // XOR value
    if (!flag) numbers.add(candidate);
  }
 
  // Print all the values obtained
  for (let x of numbers) {
    document.write(x + " ");
  }
}
 
// Driver Code
let A = [7, 8, 14];
let B = [5, 12, 3];
let N = A.length;
findPossibleValues(A, B, N);
 
// This code is contributed by gfgking.
</script>

Producción:

Complejidad de tiempo: O(N ² *log(N))
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior también se puede optimizar al no ordenar la array y almacenar el XOR bit a bit de todos los elementos de B[] , y luego el XOR bit a bit con todos los elementos en C[] . Ahora, si el resultado es 0 , significa que ambas arrays tienen los mismos elementos. Siga los pasos a continuación para resolver el problema:

Inicialice la variable, digamos x que almacena el XOR de todos los elementos de la array B[].
Inicialice un conjunto , diga números [] para almacenar solo números únicos.
Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
- Inicialice las variables candidatas como XOR de A[0] y B[i] y curr_xor como x para ver si es 0 después de realizar las operaciones requeridas.
- Iterar sobre el rango [0, N) usando la variable j y realizar los siguientes pasos:
  - Inicialice la variable y como el XOR de A[j] y el candidato y XOR y con curr_xor.
- Si curr_xor es igual a 0, inserte el candidato de valor en el conjunto de números [].
Después de realizar los pasos anteriores, imprima los números establecidos [] como 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 find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
void findPossibleValues(int A[], int B[],
                        int n)
{
    // Stores the XOR of the array B[]
    int x = 0;
 
    for (int i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    set<int> numbers;
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
        int curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            int y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.insert(candidate);
    }
 
    // Print all the possible value
    for (auto x : numbers) {
        cout << x << " ";
    }
}
 
// Driver Code
int main()
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findPossibleValues(A, B, N);
 
    return 0;
}

Java

// Java code for above approach
import java.util.*;
 
class GFG{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int A[], int B[],
                        int n)
{
    // Stores the XOR of the array B[]
    int x = 0;
 
    for (int i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    HashSet<Integer> numbers = new HashSet<Integer>();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
        int curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            int y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.add(candidate);
    }
 
    // Print all the possible value
    for (int i : numbers) {
        System.out.print(i + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 7, 8, 14 };
    int B[] = { 5, 12, 3 };
    int N = A.length;
    findPossibleValues(A, B, N);
}
}
 
// This code is contributed by avijitmondal1998.

Python3

# Python 3 program for the above approach
 
# Function to find all possible values
# of Bitwise XOR such after rearranging
# the array elements the Bitwise XOR
# value at corresponding indexes is same
def findPossibleValues(A, B, n):
   
    # Stores the XOR of the array B[]
    x = 0
 
    for i in range(n):
        x = x ^ B[i]
 
    # Stores all possible value of
    # Bitwise XOR
    numbers = set()
 
    # Iterate over the range
    for i in range(n):
        # Possible value of K
        candidate = A[0] ^ B[i]
        curr_xor = x
 
        # Array B for the considered
        # value of K
        for j in range(n):
            y = A[j] ^ candidate
            curr_xor = curr_xor ^ y
 
        # This means all the elements
        # are equal
        if (curr_xor == 0):
            numbers.add(candidate)
 
    # Print all the possible value
    for x in numbers:
        print(x, end = " ")
 
# Driver Code
if __name__ == '__main__':
    A = [7, 8, 14]
    B = [5, 12, 3]
    N = len(A)
    findPossibleValues(A, B, N)
     
    # This code is contributed by ipg2016107.

C#

// C# code for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
static void findPossibleValues(int []A, int []B,
                        int n)
{
   
    // Stores the XOR of the array []B
    int x = 0;
 
    for (int i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    HashSet<int> numbers = new HashSet<int>();
 
    // Iterate over the range
    for (int i = 0; i < n; i++) {
 
        // Possible value of K
        int candidate = A[0] ^ B[i];
        int curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (int j = 0; j < n; j++) {
            int y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.Add(candidate);
    }
 
    // Print all the possible value
    foreach (int i in numbers) {
        Console.Write(i + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 7, 8, 14 };
    int []B = { 5, 12, 3 };
    int N = A.Length;
    findPossibleValues(A, B, N);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// javascript code for above approach
 
// Function to find all possible values
// of Bitwise XOR such after rearranging
// the array elements the Bitwise XOR
// value at corresponding indexes is same
function findPossibleValues(A, B, n)
{
 
    // Stores the XOR of the array B
    var x = 0;
 
    for (var i = 0; i < n; i++) {
        x = x ^ B[i];
    }
 
    // Stores all possible value of
    // Bitwise XOR
    var numbers = new Set();
 
    // Iterate over the range
    for (var i = 0; i < n; i++) {
 
        // Possible value of K
        var candidate = A[0] ^ B[i];
        var curr_xor = x;
 
        // Array B for the considered
        // value of K
        for (var j = 0; j < n; j++) {
            var y = A[j] ^ candidate;
            curr_xor = curr_xor ^ y;
        }
 
        // This means all the elements
        // are equal
        if (curr_xor == 0)
            numbers.add(candidate);
    }
 
    // Print all the possible value
    for (var i of numbers) {
        document.write(i + " ");
    }
}
 
// Driver Code
var A = [ 7, 8, 14 ];
var B = [ 5, 12, 3 ];
var N = A.length;
findPossibleValues(A, B, N);
 
// This code is contributed by shikhasingrajput
</script>

Producción:

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta