Dada una array arr[] que consta de N enteros, la tarea es encontrar el XOR bit a bit máximo de todos los pares posibles en la array dada .
Ejemplos:
Entrada: arr[] = {25, 10, 2, 8, 5, 3}
Salida: 28
Explicación:
El resultado máximo es 5^25 = 28.Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida: 7
Explicación:
El resultado máximo es 1^6 = 7.
Enfoque ingenuo: consulte el artículo XOR máximo de dos números en una array para conocer el enfoque más simple para resolver el problema generando todos los pares de la array dada y calculando el XOR de cada par para encontrar el máximo entre ellos.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque de enmascaramiento de bits: consulte el artículo XOR máximo de dos números en una array para resolver el problema con el enmascaramiento de bits .
Complejidad de Tiempo: O(N*log M), donde M es el número máximo presente en el arreglo
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede resolver utilizando Trie insertando la representación binaria de los números en la array arr[] . Ahora itere la representación binaria de todos los elementos en la array arr[] y si el bit actual es 0 , busque la ruta con el valor 1 o viceversa en Trie para obtener el valor máximo de Bitwise XOR . Actualiza el valor máximo de cada número. A continuación se muestran los pasos:
- Inicialice máximoXOR como 0 .
- Inserte la representación binaria de todos los números en la array dada arr[] en el Árbol. Al insertar en el trie si el bit actual es 0 , cree un Node a la izquierda; de lo contrario, cree un Node a la derecha del Node principal actual.
- Ahora, recorra la array dada y para cada elemento haga lo siguiente:
- Inicialice el valor XOR actual como 0.
- Atraviesa la representación binaria del número actual.
- Si i -th bit es 1 y node->left existe, actualice currentXOR como currentXOR + pow(2, i) y actualice node como node->left . De lo contrario, actualice node = node->right .
- Si i -th bit es 0 , y node->right existe, actualice currentXOR como currentXOR + pow(2, i) y actualice node como node->right . De lo contrario, actualice node = node->left .
- Para cada elemento de la array en el paso anterior, actualice el valor de maximumXOR si maximumXOR es mayor que currentXOR .
- Imprime el valor de maximumXOR después de los pasos anteriores.
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;
// Structure of Trie
class node {
public:
node* left;
node* right;
};
// Function to insert binary
// representation of element x
// in the Trie
void insert(int x, node* head)
{
// Store the head
node* curr = head;
for (int i = 30; i >= 0; i--) {
// Find the i-th bit
int val = (x >> i) & 1;
if (val == 0) {
// If curr->left is NULL
if (!curr->left)
curr->left = new node();
// Update curr to curr->left
curr = curr->left;
}
else {
// If curr->right is NULL
if (!curr->right)
curr->right = new node();
// Update curr to curr->right
curr = curr->right;
}
}
}
// Function that finds the maximum
// Bitwise XOR value for all such pairs
int findMaximumXOR(int arr[], int n)
{
// head Node of Trie
node* head = new node();
// Insert each element in trie
for (int i = 0; i < n; i++) {
insert(arr[i], head);
}
// Stores the maximum XOR value
int ans = 0;
// Traverse the given array
for (int i = 0; i < n; i++) {
// Stores the XOR with current
// value arr[i]
int curr_xor = 0;
int M = pow(2, 30);
node* curr = head;
for (int j = 30; j >= 0; j--) {
// Finding ith bit
int val = (arr[i] >> j) & 1;
// Check if the bit is 0
if (val == 0) {
// If right node exists
if (curr->right) {
// Update the currentXOR
curr_xor += M;
curr = curr->right;
}
else {
curr = curr->left;
}
}
else {
// Check if left node exists
if (curr->left) {
// Update the currentXOR
curr_xor += M;
curr = curr->left;
}
else {
curr = curr->right;
}
}
// Update M to M/2 for next set bit
M /= 2;
}
// Update the maximum XOR
ans = max(ans, curr_xor);
}
// Return the maximum XOR found
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << findMaximumXOR(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Structure of Trie
static class node
{
node left;
node right;
};
// Function to insert binary
// representation of element x
// in the Trie
static void insert(int x, node head)
{
// Store the head
node curr = head;
for(int i = 30; i >= 0; i--)
{
// Find the i-th bit
int val = (x >> i) & 1;
if (val == 0)
{
// If curr.left is null
if (curr.left == null)
curr.left = new node();
// Update curr to curr.left
curr = curr.left;
}
else
{
// If curr.right is null
if (curr.right == null)
curr.right = new node();
// Update curr to curr.right
curr = curr.right;
}
}
}
// Function that finds the maximum
// Bitwise XOR value for all such pairs
static int findMaximumXOR(int arr[], int n)
{
// head Node of Trie
node head = new node();
// Insert each element in trie
for(int i = 0; i < n; i++)
{
insert(arr[i], head);
}
// Stores the maximum XOR value
int ans = 0;
// Traverse the given array
for(int i = 0; i < n; i++)
{
// Stores the XOR with current
// value arr[i]
int curr_xor = 0;
int M = (int)Math.pow(2, 30);
node curr = head;
for(int j = 30; j >= 0; j--)
{
// Finding ith bit
int val = (arr[i] >> j) & 1;
// Check if the bit is 0
if (val == 0)
{
// If right node exists
if (curr.right != null)
{
// Update the currentXOR
curr_xor += M;
curr = curr.right;
}
else
{
curr = curr.left;
}
}
else
{
// Check if left node exists
if (curr.left != null)
{
// Update the currentXOR
curr_xor += M;
curr = curr.left;
}
else
{
curr = curr.right;
}
}
// Update M to M/2 for next set bit
M /= 2;
}
// Update the maximum XOR
ans = Math.max(ans, curr_xor);
}
// Return the maximum XOR found
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
// Function call
System.out.print(findMaximumXOR(arr, N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python program for the above approach # Structure of Trie class node: def __init__(self): self.left = None self.right = None # Function to insert binary # representation of element x # in the Trie def insert(x, head): # Store the head curr = head for i in range(30, -1, -1): # Find the i-th bit val = (x >> i) & 1 if (val == 0): # If curr.left is null if (curr.left == None): curr.left = node() # Update curr to curr.left curr = curr.left else: # If curr.right is null if (curr.right == None): curr.right = node() # Update curr to curr.right curr = curr.right # Function that finds the maximum # Bitwise XOR value for all such pairs def findMaximumXOR(arr, n): # head Node of Trie head = node() # Insert each element in trie for i in range(n): insert(arr[i], head) # Stores the maximum XOR value ans = 0 # Traverse the given array for i in range(n): # Stores the XOR with current # value arr[i] curr_xor = 0 M = 2 ** 30 curr = head for j in range(30, -1, -1): # Finding ith bit val = (arr[i] >> j) & 1 # Check if the bit is 0 if (val == 0): # If right node exists if (curr.right != None): # Update the currentXOR curr_xor += M curr = curr.right else: curr = curr.left else: # Check if left node exists if (curr.left != None): # Update the currentXOR curr_xor += M curr = curr.left else: curr = curr.right # Update M to M/2 for next set bit M = M//2 # Update the maximum XOR ans = max(ans, curr_xor) # Return the maximum XOR found return ans # Driver Code # Given array arr arr = [1, 2, 3, 4] N = len(arr) # Function call print(findMaximumXOR(arr, N)) # This code is contributed by Saurbah Jaiswal
C#
// C# program for
// the above approach
using System;
class GFG{
// Structure of Tree
public class node
{
public node left;
public node right;
};
// Function to insert binary
// representation of element
// x in the Tree
static void insert(int x,
node head)
{
// Store the head
node curr = head;
for(int i = 30; i >= 0; i--)
{
// Find the i-th bit
int val = (x >> i) & 1;
if (val == 0)
{
// If curr.left is null
if (curr.left == null)
curr.left = new node();
// Update curr to curr.left
curr = curr.left;
}
else
{
// If curr.right is null
if (curr.right == null)
curr.right = new node();
// Update curr to curr.right
curr = curr.right;
}
}
}
// Function that finds the maximum
// Bitwise XOR value for all
// such pairs
static int findMaximumXOR(int []arr,
int n)
{
// Head Node of Tree
node head = new node();
// Insert each element in tree
for(int i = 0; i < n; i++)
{
insert(arr[i], head);
}
// Stores the maximum XOR value
int ans = 0;
// Traverse the given array
for(int i = 0; i < n; i++)
{
// Stores the XOR with
// current value arr[i]
int curr_xor = 0;
int M = (int)Math.Pow(2, 30);
node curr = head;
for(int j = 30; j >= 0; j--)
{
// Finding ith bit
int val = (arr[i] >> j) & 1;
// Check if the bit is 0
if (val == 0)
{
// If right node exists
if (curr.right != null)
{
// Update the currentXOR
curr_xor += M;
curr = curr.right;
}
else
{
curr = curr.left;
}
}
else
{
// Check if left node exists
if (curr.left != null)
{
// Update the currentXOR
curr_xor += M;
curr = curr.left;
}
else
{
curr = curr.right;
}
}
// Update M to M/2
// for next set bit
M /= 2;
}
// Update the maximum XOR
ans = Math.Max(ans, curr_xor);
}
// Return the maximum
// XOR found
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 2, 3, 4};
int N = arr.Length;
// Function call
Console.Write(findMaximumXOR(arr, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program for the above approach
// Structure of Trie
class node {
constructor() {
this.left = null;
this.right = null;
}
}
// Function to insert binary
// representation of element x
// in the Trie
function insert(x, head) {
// Store the head
var curr = head;
for (i = 30; i >= 0; i--) {
// Find the i-th bit
var val = (x >> i) & 1;
if (val == 0) {
// If curr.left is null
if (curr.left == null)
curr.left = new node();
// Update curr to curr.left
curr = curr.left;
} else {
// If curr.right is null
if (curr.right == null)
curr.right = new node();
// Update curr to curr.right
curr = curr.right;
}
}
}
// Function that finds the maximum
// Bitwise XOR value for all such pairs
function findMaximumXOR(arr , n) {
// head Node of Trie
var head = new node();
// Insert each element in trie
for (var i = 0; i < n; i++) {
insert(arr[i], head);
}
// Stores the maximum XOR value
var ans = 0;
// Traverse the given array
for (i = 0; i < n; i++) {
// Stores the XOR with current
// value arr[i]
var curr_xor = 0;
var M = parseInt( Math.pow(2, 30));
var curr = head;
for (j = 30; j >= 0; j--) {
// Finding ith bit
var val = (arr[i] >> j) & 1;
// Check if the bit is 0
if (val == 0) {
// If right node exists
if (curr.right != null) {
// Update the currentXOR
curr_xor += M;
curr = curr.right;
} else {
curr = curr.left;
}
}
else {
// Check if left node exists
if (curr.left != null) {
// Update the currentXOR
curr_xor += M;
curr = curr.left;
} else {
curr = curr.right;
}
}
// Update M to M/2 for next set bit
M = parseInt(M/2);
}
// Update the maximum XOR
ans = Math.max(ans, curr_xor);
}
// Return the maximum XOR found
return ans;
}
// Driver Code
// Given array arr
var arr = [ 1, 2, 3, 4 ];
var N = arr.length;
// Function call
document.write(findMaximumXOR(arr, N));
// This code is contributed by umadevi9616
</script>
Producción:
7
Complejidad temporal: O(32*N)
Espacio auxiliar: O(32*N)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA