Reorganizar la array para hacer Bitwise XOR de elementos indexados similares de dos arrays es lo mismo

Posted on by Rudeus Greyrat

Dadas dos arrays A[] y B[] que constan de N enteros ( N es impar), la tarea es reorganizar la array B[] de modo que para cada 1 ≤ i ≤ N , Bitwise XOR de A[i] y B[i ] es lo mismo. Si no es posible tal reordenamiento, escriba “-1” . De lo contrario, imprima el reordenamiento.

Ejemplos:

Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1} Salida: {1, 2, 3, 4, 5}
Explicación :
Reorganizar
el array B[] a {1, 2, 3, 4, 5}, Bitwise XOR entre cada par correspondiente de elementos de array es el mismo, es decir, 0.

Entrada: A[] = {14, 21, 33, 49, 53}, B[] = {54, 50, 34, 22, 14}
Salida: -1

Enfoque ingenuo: el enfoque más simple es generar todos los arreglos posibles de la array B[] e imprimir las combinaciones de la array cuyo Bitwise XOR con los elementos correspondientes es el mismo. 

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

Enfoque eficiente: la idea es utilizar la propiedad conmutativa de Bitwise XOR . A continuación se muestran los pasos:

  • Encuentre el XOR bit a bit de ambos elementos de la array, deje que el valor sea xor_value .
  • Almacene la frecuencia del elemento de la array B[] en un mapa M .
  • Para reorganizar los elementos de la array de B[], recorra la array B[] y haga lo siguiente:
    • Actualice el elemento actual de esta array como A[i]^xor_value .
    • Si la frecuencia del elemento actual actualizado es mayor que 1, entonces disminúyalo.
    • De lo contrario, no existe tal arreglo posible, salga del bucle e imprima «-1» .
  • Después de completar los pasos anteriores, imprima la array B[] , ya que contiene la array reorganizada.

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 rearrange the array
// B[] such that A[i] ^ B[i] is same
// for each element
vector<int> rearrangeArray(
    vector<int>& A, vector<int>& B, int N)
{
    // Store frequency of elements
    map<int, int> m;
 
    // Stores xor value
    int xor_value = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Taking xor of all the
        // values of both arrays
        xor_value ^= A[i];
        xor_value ^= B[i];
 
        // Store frequency of B[]
        m[B[i]]++;
    }
 
    for (int i = 0; i < N; i++) {
 
        // Find the array B[] after
        // rearrangement
        B[i] = A[i] ^ xor_value;
 
        // If the updated value is
        // present then decrement
        // its frequency
        if (m[B[i]]) {
            m[B[i]]--;
        }
 
        // Otherwise return empty vector
        else
            return vector<int>{};
    }
 
    return B;
}
 
// Utility function to rearrange the
// array B[] such that A[i] ^ B[i]
// is same for each element
void rearrangeArrayUtil(
    vector<int>& A, vector<int>& B, int N)
{
    // Store rearranged array B
    vector<int> ans
        = rearrangeArray(A, B, N);
 
    // If rearrangement possible
    if (ans.size()) {
        for (auto x : ans) {
            cout << x << " ";
        }
    }
 
    // Otherwise return -1
    else {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
    // Given vector A
    vector<int> A = { 13, 21, 33, 49, 53 };
 
    // Given vector B
    vector<int> B = { 54, 50, 34, 22, 14 };
 
    // Size of the vector
    int N = (int)A.size();
 
    // Function Call
    rearrangeArrayUtil(A, B, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to rearrange the array
// B[] such that A[i] ^ B[i] is same
// for each element
static ArrayList<Integer> rearrangeArray(
       ArrayList<Integer> A,
       ArrayList<Integer> B, int N)
{
     
    // Store frequency of elements
    HashMap<Integer,
            Integer> m = new HashMap<Integer,
                                     Integer>();
 
    // Stores xor value
    int xor_value = 0;
 
    for(int i = 0; i < N; i++)
    {
         
        // Taking xor of all the
        // values of both arrays
        xor_value ^= A.get(i);
        xor_value ^= B.get(i);
 
        // Store frequency of B[]
        m.put(B.get(i),
              m.getOrDefault(B.get(i) + 1, 0));
    }
 
    for(int i = 0; i < N; i++)
    {
         
        // Find the array B[] after
        // rearrangement
        B.set(i, A.get(i) ^ xor_value);
 
        // If the updated value is
        // present then decrement
        // its frequency
        if (m.getOrDefault(B.get(i), -1) != -1)
        {
            m.put(B.get(i),
                  m.getOrDefault(B.get(i), 0) - 1);
        }
 
        // Otherwise return empty vector
        else
            return (new ArrayList<Integer>());
    }
    return B;
}
 
// Utility function to rearrange the
// array B[] such that A[i] ^ B[i]
// is same for each element
static void rearrangeArrayUtil(ArrayList<Integer> A,
                               ArrayList<Integer> B, int N)
{
     
    // Store rearranged array B
    ArrayList<Integer> ans = rearrangeArray(A, B, N);
 
    // If rearrangement possible
    if (ans.size() != 0)
    {
        for(int i = 0; i < ans.size(); i++)
        {
            System.out.print(ans.get(i) + " ");
        }
    }
 
    // Otherwise return -1
    else
    {
        System.out.println("-1");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given vector A
    ArrayList<Integer> A = new ArrayList<Integer>(
        Arrays.asList(13, 21, 33, 49, 53));
 
    // Given vector B
    ArrayList<Integer> B = new ArrayList<Integer>(
        Arrays.asList(54, 50, 34, 22, 14));
 
    // Size of the vector
    int N = (int)A.size();
 
    // Function Call
    rearrangeArrayUtil(A, B, N);
}
}
 
// This code is contributed by akhilsaini

Python3

# Python3 program for the above approach
 
# Function to rearrange the array
# B[] such that A[i] ^ B[i] is same
# for each element
def rearrangeArray(A, B, N):
   
  # Store frequency of elements
  m = {}
 
  # Stores xor value
  xor_value = 0
 
  for i in range(0, N):
     
    # Taking xor of all the
    # values of both arrays
    xor_value ^= A[i]
    xor_value ^= B[i]
 
    # Store frequency of B[]
    if B[i] in m:
      m[B[i]] = m[B[i]] + 1
    else:
      m[B[i]] = 1
     
  for i in range(0, N):
     
    # Find the array B[] after
    # rearrangement
    B[i] = A[i] ^ xor_value
 
    # If the updated value is
    # present then decrement
    # its frequency
    if B[i] in m:
      m[B[i]] = m[B[i]] - 1
       
    # Otherwise return empty vector
    else:
      X = []
      return X
 
  return B
 
# Utility function to rearrange the
# array B[] such that A[i] ^ B[i]
# is same for each element
def rearrangeArrayUtil(A, B, N):
   
  # Store rearranged array B
  ans = rearrangeArray(A, B, N)
   
  # If rearrangement possible
  if (len(ans) > 0):
     for x in ans:
        print(x, end = ' ')
         
  # Otherwise return -1
  else:
    print("-1")
     
# Driver Code
if __name__ == '__main__':
   
  # Given vector A
  A = [ 13, 21, 33, 49, 53 ]
 
  # Given vector B
  B = [ 54, 50, 34, 22, 14 ]
 
  # Size of the vector
  N = len(A)
 
  # Function Call
  rearrangeArrayUtil(A, B, N)
   
# This code is contributed by akhilsaini

C#

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
 
// Function to rearrange the array
// B[] such that A[i] ^ B[i] is same
// for each element
static ArrayList rearrangeArray(ArrayList A,
                                ArrayList B, int N)
{
     
    // Store frequency of elements
    Dictionary<int,
               int> m = new Dictionary<int,
                                       int>();
 
    // Stores xor value
    int xor_value = 0;
 
    for(int i = 0; i < N; i++)
    {
         
        // Taking xor of all the
        // values of both arrays
        xor_value ^= (int)A[i];
        xor_value ^= (int)B[i];
 
        // Store frequency of B[]
        if (!m.ContainsKey((int)B[i]))
            m.Add((int)B[i], 1);
        else
            m[(int)B[i]] = m[(int)B[i]] + 1;
    }
 
    for(int i = 0; i < N; i++)
    {
         
        // Find the array B[] after
        // rearrangement
        B[i] = (int)A[i] ^ xor_value;
 
        // If the updated value is
        // present then decrement
        // its frequency
        if (m.ContainsKey((int)B[i]))
        {
            m[(int)B[i]]--;
        }
 
        // Otherwise return empty vector
        else
            return (new ArrayList());
    }
    return B;
}
 
// Utility function to rearrange the
// array B[] such that A[i] ^ B[i]
// is same for each element
static void rearrangeArrayUtil(ArrayList A,
                               ArrayList B,
                               int N)
{
     
    // Store rearranged array B
    ArrayList ans = rearrangeArray(A, B, N);
 
    // If rearrangement possible
    if (ans.Count != 0)
    {
        for(int i = 0; i < ans.Count; i++)
        {
            Console.Write(ans[i] + " ");
        }
    }
     
    // Otherwise return -1
    else
    {
        Console.WriteLine("-1");
    }
}
 
// Driver Code
public static void Main()
{
     
    // Given vector A
    ArrayList A = new ArrayList{ 13, 21, 33, 49, 53 };
 
    // Given vector B
    ArrayList B = new ArrayList{ 54, 50, 34, 22, 14 };
 
    // Size of the vector
    int N = A.Count;
 
    // Function Call
    rearrangeArrayUtil(A, B, N);
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
// Javascript program for the above approach
 
// Function to rearrange the array
// B[] such that A[i] ^ B[i] is same
// for each element
function rearrangeArray(A, B, N)
{
 
    // Store frequency of elements
    let m = new Map();
 
    // Stores xor value
    let xor_value = 0;
 
    for (let i = 0; i < N; i++) {
 
        // Taking xor of all the
        // values of both arrays
        xor_value ^= A[i];
        xor_value ^= B[i];
 
        // Store frequency of B[]
        if (m.has(B[i])) {
            m.set(B[i], m.get(B[i]) + 1)
        } else {
            m.set(B[i], 1)
        }
    }
 
    for (let i = 0; i < N; i++) {
 
        // Find the array B[] after
        // rearrangement
        B[i] = A[i] ^ xor_value;
 
        // If the updated value is
        // present then decrement
        // its frequency
        if (m.has(B[i])) {
            m.set(B[i], m.get(B[i]) - 1)
        }
 
        // Otherwise return empty vector
        else
            return [];
    }
 
    return B;
}
 
// Utility function to rearrange the
// array B[] such that A[i] ^ B[i]
// is same for each element
function rearrangeArrayUtil(A, B, N)
{
 
    // Store rearranged array B
    let ans = rearrangeArray(A, B, N);
 
    // If rearrangement possible
    if (ans.length > 0) {
        for (let x of ans) {
            document.write(x + " ");
        }
    }
 
    // Otherwise return -1
    else {
        document.write("-1");
    }
}
 
// Driver Code
 
// Given vector A
let A = [13, 21, 33, 49, 53];
 
// Given vector B
let B = [54, 50, 34, 22, 14];
 
// Size of the vector
let N = A.length;
 
// Function Call
rearrangeArrayUtil(A, B, N);
 
// This code is contributed by _saurabh_jaiswal.
</script>
Producción: 

14 22 34 50 54

 

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

Publicación traducida automáticamente

Artículo escrito por vshlparmar4 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 *