Se dan dos arrays A y B que constan de N elementos. La tarea es calcular el XOR máximo posible de cada elemento en la array A con la array B.
Ejemplos:
Input : A : 7 3 9 12 B : 1 3 5 2 Output : 6 6 12 15 Explanation : 1 xor 7 = 6, 5 xor 3 = 6, 5 xor 9 = 12, 3 xor 12 = 15.
Un enfoque ingenuo para resolver este problema sería verificar cada elemento de la array A con todos los demás elementos de la array B e imprimir el xor máximo.
Complejidad de tiempo: O (n ^ 2)
Una solución eficiente es utilizar Trie Data Structure .
We maintain a Trie for the binary representation of all elements in array B. Now, for every element of A, we find the maximum xor in trie. Let's say our number A[i] is {b1, b2...bn}, where b1, b2...bn are binary bits. We start from b1. Now for the xor to be maximum, we'll try to make most significant bit 1 after performing the xor. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favourable option is not there, we'll go other side. Doing this all over, we'll get the maximum XOR possible.
A continuación se muestra la implementación.
C++
// C++ code to find the maximum possible X-OR of
// every array element with another array
#include<bits/stdc++.h>
using namespace std;
// Structure of Trie DS
struct trie
{
int value;
trie *child[2];
};
// Function to initialise a Trie Node
trie * get()
{
trie * root = new trie;
root -> value = 0;
root -> child[0] = NULL;
root -> child[1] = NULL;
return root;
}
// Computing max xor
int max_xor(trie * root, int key)
{
trie * temp = root;
// Checking for all bits in integer range
for (int i = 31; i >= 0; i--)
{
// Current bit in the number
bool current_bit = ( key & ( 1 << i) );
// Traversing Trie for different bit, if found
if (temp -> child[1 - current_bit] != NULL)
temp = temp -> child[1 - current_bit];
// Traversing Trie for same bit
else
temp = temp -> child[current_bit];
}
// Returning xor value of maximum bit difference
// value. Thus, we get maximum xor value
return (key ^ temp -> value);
}
// Inserting B[] in Trie
void insert(trie * root, int key)
{
trie * temp = root;
// Storing 31 bits as integer representation
for (int i = 31; i >= 0; i--)
{
// Current bit in the number
bool current_bit = key & (1 << i);
// New node required
if (temp -> child[current_bit] == NULL)
temp -> child[current_bit] = get();
// Traversing in Trie
temp = temp -> child[current_bit];
}
// Assigning value to the leaf Node
temp -> value = key;
}
int main()
{
int A[] = {7, 3, 9, 12};
int B[] = {1, 3, 5, 2};
int N = sizeof(A)/sizeof(A[0]);
// Forming Trie for B[]
trie * root = get();
for (int i = 0; i < N; i++)
insert(root, B[i]);
for (int i = 0; i < N; i++)
cout << max_xor(root, A[i]) << endl;
return 0;
}
Java
// Java code to find the maximum possible X-OR of
// every array element with another array
import java.util.*;
class GFG
{
// Structure of Trie DS
static class trie
{
int value;
trie []child = new trie[2];
};
// Function to initialise a Trie Node
static trie get()
{
trie root = new trie();
root.value = 0;
root.child[0] = null;
root.child[1] = null;
return root;
}
// Computing max xor
static int max_xor(trie root, int key)
{
trie temp = root;
// Checking for all bits in integer range
for (int i = 31; i >= 0; i--)
{
// Current bit in the number
int current_bit = (key & (1 << i));
if(current_bit > 0)
current_bit = 1;
// Traversing Trie for different bit, if found
if (temp.child[1 - current_bit] != null)
temp = temp.child[1 - current_bit];
// Traversing Trie for same bit
else
temp = temp.child[current_bit];
}
// Returning xor value of maximum bit difference
// value. Thus, we get maximum xor value
return (key ^ temp.value);
}
// Inserting B[] in Trie
static void insert(trie root, int key)
{
trie temp = root;
// Storing 31 bits as integer representation
for (int i = 31; i >= 0; i--)
{
// Current bit in the number
int current_bit = key & (1 << i);
if(current_bit > 0)
current_bit = 1;
//System.out.println(current_bit);
// New node required
if (temp.child[current_bit] == null)
temp.child[current_bit] = get();
// Traversing in Trie
temp = temp.child[current_bit];
}
// Assigning value to the leaf Node
temp.value = key;
}
// Driver Code
public static void main(String[] args)
{
int A[] = {7, 3, 9, 12};
int B[] = {1, 3, 5, 2};
int N = A.length;
// Forming Trie for B[]
trie root = get();
for (int i = 0; i < N; i++)
insert(root, B[i]);
for (int i = 0; i < N; i++)
System.out.println(max_xor(root, A[i]));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 code to find the maximum # possible X-OR of every array # element with another array # Structure of Trie DS class trie: def __init__(self, value: int = 0) -> None: self.value = value self.child = [None] * 2 # Function to initialise a Trie Node def get() -> trie: root = trie() root.value = 0 root.child[0] = None root.child[1] = None return root # Computing max xor def max_xor(root: trie, key: int) -> int: temp = root # Checking for all bits in integer range for i in range(31, -1, -1): # Current bit in the number current_bit = (key & (1 << i)) if (current_bit > 0): current_bit = 1 # Traversing Trie for different bit, if found if (temp.child[1 - current_bit] != None): temp = temp.child[1 - current_bit] # Traversing Trie for same bit else: temp = temp.child[current_bit] # Returning xor value of maximum bit difference # value. Thus, we get maximum xor value return (key ^ temp.value) # Inserting B[] in Trie def insert(root: trie, key: int) -> None: temp = root # Storing 31 bits as integer representation for i in range(31, -1, -1): # Current bit in the number current_bit = key & (1 << i) if (current_bit > 0): current_bit = 1 # New node required if (temp.child[current_bit] == None): temp.child[current_bit] = get() # Traversing in Trie temp = temp.child[current_bit] # Assigning value to the leaf Node temp.value = key # Driver Code if __name__ == "__main__": A = [ 7, 3, 9, 12 ] B = [ 1, 3, 5, 2 ] N = len(A) # Forming Trie for B[] root = get() for i in range(N): insert(root, B[i]) for i in range(N): print(max_xor(root, A[i])) # This code is contributed by sanjeev2552
C#
// C# code to find the maximum possible X-OR of
// every array element with another array
using System;
class GFG
{
// Structure of Trie DS
class trie
{
public int value;
public trie []child = new trie[2];
};
// Function to initialise a Trie Node
static trie get()
{
trie root = new trie();
root.value = 0;
root.child[0] = null;
root.child[1] = null;
return root;
}
// Computing max xor
static int max_xor(trie root, int key)
{
trie temp = root;
// Checking for all bits in integer range
for (int i = 31; i >= 0; i--)
{
// Current bit in the number
int current_bit = (key & (1 << i));
if(current_bit > 0)
current_bit = 1;
// Traversing Trie for different bit, if found
if (temp.child[1 - current_bit] != null)
temp = temp.child[1 - current_bit];
// Traversing Trie for same bit
else
temp = temp.child[current_bit];
}
// Returning xor value of maximum bit difference
// value. Thus, we get maximum xor value
return (key ^ temp.value);
}
// Inserting B[] in Trie
static void insert(trie root, int key)
{
trie temp = root;
// Storing 31 bits as integer representation
for (int i = 31; i >= 0; i--)
{
// Current bit in the number
int current_bit = key & (1 << i);
if(current_bit > 0)
current_bit = 1;
// System.out.println(current_bit);
// New node required
if (temp.child[current_bit] == null)
temp.child[current_bit] = get();
// Traversing in Trie
temp = temp.child[current_bit];
}
// Assigning value to the leaf Node
temp.value = key;
}
// Driver Code
public static void Main(String[] args)
{
int []A = {7, 3, 9, 12};
int []B = {1, 3, 5, 2};
int N = A.Length;
// Forming Trie for B[]
trie root = get();
for (int i = 0; i < N; i++)
insert(root, B[i]);
for (int i = 0; i < N; i++)
Console.WriteLine(max_xor(root, A[i]));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript code to find the maximum possible X-OR of
// every array element with another array
// Structure of Trie DS
class trie
{
constructor()
{
this.value=0;
this.child = new Array(2);
}
}
// Function to initialise a Trie Node
function get()
{
let root = new trie();
root.value = 0;
root.child[0] = null;
root.child[1] = null;
return root;
}
// Computing max xor
function max_xor(root,key)
{
let temp = root;
// Checking for all bits in integer range
for (let i = 31; i >= 0; i--)
{
// Current bit in the number
let current_bit = (key & (1 << i));
if(current_bit > 0)
current_bit = 1;
// Traversing Trie for different bit, if found
if (temp.child[1 - current_bit] != null)
temp = temp.child[1 - current_bit];
// Traversing Trie for same bit
else
temp = temp.child[current_bit];
}
// Returning xor value of maximum bit difference
// value. Thus, we get maximum xor value
return (key ^ temp.value);
}
// Inserting B[] in Trie
function insert(root,key)
{
let temp = root;
// Storing 31 bits as integer representation
for (let i = 31; i >= 0; i--)
{
// Current bit in the number
let current_bit = key & (1 << i);
if(current_bit > 0)
current_bit = 1;
//System.out.println(current_bit);
// New node required
if (temp.child[current_bit] == null)
temp.child[current_bit] = get();
// Traversing in Trie
temp = temp.child[current_bit];
}
// Assigning value to the leaf Node
temp.value = key;
}
// Driver Code
let A=[7, 3, 9, 12];
let B=[1, 3, 5, 2];
let N = A.length;
// Forming Trie for B[]
let root = get();
for (let i = 0; i < N; i++)
insert(root, B[i]);
for (let i = 0; i < N; i++)
document.write(max_xor(root, A[i])+"<br>");
// This code is contributed by rag2127
</script>
Producción
6 6 12 15
Trie formación: O(N x MAX_BITS) donde MAX_BITS es el número máximo de bits en representación binaria de números.
Cálculo de la diferencia máxima de bits: O (N x MAX_BITS)
Complejidad de tiempo: O (N x MAX_BITS)
Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA