Dada una array Arr de enteros no negativos de tamaño N . La tarea es encontrar el xor máximo posible entre dos números presentes en la array.
Ejemplo :
Entrada: Arr = {25, 10, 2, 8, 5, 3}
Salida: 28
Explicación: El resultado máximo es 5 ^ 25 = 28Entrada: Arr = {1, 2, 3, 4, 5, 6, 7}
Salida: 7
Explicación: El resultado máximo es 1 ^ 6 = 7
Enfoque ingenuo: una solución simple es generar todos los pares de la array dada y calcular el XOR de los pares. Finalmente, devuelva el valor XOR máximo. Esta solución lleva 
tiempo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// maximum xor
int max_xor(int arr[], int n)
{
int maxXor = 0;
// Calculating xor of each pair
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxXor = max(maxXor,
arr[i] ^ arr[j]);
}
}
return maxXor;
}
// Driver Code
int main()
{
int arr[] = { 25, 10, 2, 8, 5, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << max_xor(arr, n) << endl;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the
// maximum xor
static int max_xor(int arr[], int n)
{
int maxXor = 0;
// Calculating xor of each pair
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
maxXor = Math.max(maxXor,
arr[i] ^ arr[j]);
}
}
return maxXor;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {25, 10, 2, 8, 5, 3};
int n = arr.length;
System.out.println(max_xor(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation # Function to return the # maximum xor def max_xor(arr, n): maxXor = 0; # Calculating xor of each pair for i in range(n): for j in range(i + 1, n): maxXor = max(maxXor,\ arr[i] ^ arr[j]); return maxXor; # Driver Code if __name__ == '__main__': arr = [ 25, 10, 2, 8, 5, 3 ]; n = len(arr); print(max_xor(arr, n)); # This code is contributed by 29AjayKumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// maximum xor
static int max_xor(int []arr, int n)
{
int maxXor = 0;
// Calculating xor of each pair
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
maxXor = Math.Max(maxXor,
arr[i] ^ arr[j]);
}
}
return maxXor;
}
// Driver Code
public static void Main()
{
int []arr = {25, 10, 2, 8, 5, 3};
int n = arr.Length;
Console.WriteLine(max_xor(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation
// Function to return the
// maximum xor
function max_xor(arr, n)
{
let maxXor = 0;
// Calculating xor of each pair
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
maxXor = Math.max(maxXor,
arr[i] ^ arr[j]);
}
}
return maxXor;
}
// Driver Code
let arr = [ 25, 10, 2, 8, 5, 3 ];
let n = arr.length;
document.write(max_xor(arr, n));
</script>
28
Complejidad de tiempo: O(N^{2}), donde N es el tamaño de la array
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque es similar al de este artículo, donde la tarea es encontrar el par de valores AND máximo .
Entonces, la idea es cambiar la declaración del problema de encontrar el xor máximo de dos números en una array a -> encontrar dos números en una array, de modo que xor sea igual a un número X. En este caso, X será el número máximo que queremos alcanzar hasta el i-ésimo bit.
Para encontrar el valor más grande de una operación XOR, el valor de xor debe tener todos los bits para ser un conjunto de bits, es decir, 1. En un número de 32 bits, el objetivo es obtener la mayor cantidad de 1 conjunto de izquierda a derecha.
Para evaluar cada bit, se necesita una máscara para ese bit. Una máscara define qué bit debe estar presente en la respuesta y cuál no. Aquí usaremos una máscara para mantener el prefijo para cada número (es decir, tomando las respuestas con la máscara, cuántos bits quedan del número) en la entrada hasta el i-ésimo bit y luego con la lista de posibles números en nuestro conjunto , después de insertar el número, evaluaremos si podemos actualizar el máximo para que la posición de ese bit sea 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// maximum xor
int max_xor(int arr[], int n)
{
int maxx = 0, mask = 0;
set<int> se;
for (int i = 30; i >= 0; i--) {
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for (int i = 0; i < n; ++i) {
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.insert(arr[i] & mask);
}
int newMaxx = maxx | (1 << i);
for (int prefix : se) {
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if (se.count(newMaxx ^ prefix)) {
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.clear();
}
return maxx;
}
// Driver Code
int main()
{
int arr[] = { 25, 10, 2, 8, 5, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << max_xor(arr, n) << endl;
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to return the
// maximum xor
static int max_xor(int arr[], int n)
{
int maxx = 0, mask = 0;
HashSet<Integer> se = new HashSet<Integer>();
for (int i = 30; i >= 0; i--)
{
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for (int j = 0; j < n; ++j)
{
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.add(arr[j] & mask);
}
int newMaxx = maxx | (1 << i);
for (int prefix : se)
{
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if (se.contains(newMaxx ^ prefix))
{
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.clear();
}
return maxx;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 25, 10, 2, 8, 5, 3 };
int n = arr.length;
System.out.println(max_xor(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach # Function to return the # maximum xor def max_xor( arr , n): maxx = 0 mask = 0; se = set() for i in range(30, -1, -1): # set the i'th bit in mask # like 100000, 110000, 111000.. mask |= (1 << i) newMaxx = maxx | (1 << i) for i in range(n): # Just keep the prefix till # i'th bit neglecting all # the bit's after i'th bit se.add(arr[i] & mask) for prefix in se: # find two pair in set # such that a^b = newMaxx # which is the highest # possible bit can be obtained if (newMaxx ^ prefix) in se: maxx = newMaxx break # clear the set for next # iteration se.clear() return maxx # Driver Code arr = [ 25, 10, 2, 8, 5, 3 ] n = len(arr) print(max_xor(arr, n)) # This code is contributed by ANKITKUMAR34
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the
// maximum xor
static int max_xor(int []arr, int n)
{
int maxx = 0, mask = 0;
HashSet<int> se = new HashSet<int>();
for (int i = 30; i >= 0; i--)
{
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for (int j = 0; j < n; ++j)
{
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.Add(arr[j] & mask);
}
int newMaxx = maxx | (1 << i);
foreach (int prefix in se)
{
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if (se.Contains(newMaxx ^ prefix))
{
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.Clear();
}
return maxx;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 25, 10, 2, 8, 5, 3 };
int n = arr.Length;
Console.WriteLine(max_xor(arr, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation of the above approach
// Function to return the
// maximum xor
function max_xor(arr, n)
{
let maxx = 0, mask = 0;
var se = new Set();
for (let i = 30; i >= 0; i--)
{
// set the i'th bit in mask
// like 100000, 110000, 111000..
mask |= (1 << i);
for (let j = 0; j < n; ++j)
{
// Just keep the prefix till
// i'th bit neglecting all
// the bit's after i'th bit
se.add(arr[j] & mask);
}
let newMaxx = maxx | (1 << i);
//for (let prefix in se)
for (let prefix of se.keys())
{
// find two pair in set
// such that a^b = newMaxx
// which is the highest
// possible bit can be obtained
if (se.has(newMaxx ^ prefix))
{
maxx = newMaxx;
break;
}
}
// clear the set for next
// iteration
se.clear();
}
return maxx;
}
// Driver code
let arr = [ 25, 10, 2, 8, 5, 3 ];
let n = arr.length;
document.write(max_xor(arr, n));
// This code is contributed by target_2.
</script>
28
Complejidad de Tiempo: 
, donde N es el tamaño del arreglo y M es el número máximo presente en el arreglo
Espacio Auxiliar: O(logM)
Mejor enfoque : otro enfoque sería usar una estructura Trie para almacenar la representación de bits de los números y para N términos calcular el XOR máximo que cada uno puede producir pasando por el Trie.
C++
#include <iostream>
using namespace std;
class Node {
public:
Node* one;
Node* zero;
};
class trie {
Node* root;
public:
trie() { root = new Node(); }
void insert(int n)
{
Node* temp = root;
for (int i = 31; i >= 0; i--) {
int bit = (n >> i) & 1;
if (bit == 0) {
if (temp->zero == NULL) {
temp->zero = new Node();
}
temp = temp->zero;
}
else {
if (temp->one == NULL) {
temp->one = new Node();
}
temp = temp->one;
}
}
}
int max_xor_helper(int value)
{
Node* temp = root;
int current_ans = 0;
for (int i = 31; i >= 0; i--) {
int bit = (value >> i) & 1;
if (bit == 0) {
if (temp->one) {
temp = temp->one;
current_ans += (1 << i);
}
else {
temp = temp->zero;
}
}
else {
if (temp->zero) {
temp = temp->zero;
current_ans += (1 << i);
}
else {
temp = temp->one;
}
}
}
return current_ans;
}
int max_xor(int arr[], int n)
{
int max_val = 0;
insert(arr[0]);
for (int i = 1; i < n; i++) {
max_val = max(max_xor_helper(arr[i]), max_val);
insert(arr[i]);
}
return max_val;
}
};
int main()
{
int input[] = { 25, 10, 2, 8, 5, 3 };
int n = sizeof(input) / sizeof(int);
trie t;
cout << t.max_xor(input, n);
return 0;
}
28
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por yadavakash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA