Dado un entero K y una array arr[] de tamaño N , la tarea es elegir dos elementos de la array de tal manera que el Bitwise XOR de esos dos con K (es decir, K ⊕ Primer elemento elegido ⊕ Segundo elemento elegido ) sea el maximo.
Nota: cualquier elemento de array se puede elegir tantas veces como sea posible
Ejemplos:
Entrada: N = 3, K = 2, arr[]= [1, 2, 3]
Salida: 3
Explicación: Si elegimos un elemento del segundo índice
y otro del tercer índice, entonces el XOR del triplete
será 2 ^ 2 ^ 3 = 3, que es el máximo posible.Entrada: N = 3, K = 7, arr[] = [4, 2, 3]
Salida: 7
Explicación: si elegimos ambos elementos del tercer índice,
entonces el XOR del triplete será 7 ^ 3 ^ 3 = 7 , que es el máximo posible.Entrada: N = 3, K = 3, arr[] = [1, 2, 3]
Salida: 3
Explicación: Si elegimos ambos elementos del tercer índice,
entonces el XOR del triplete será 3 ^ 3 ^ 3 = 3, que es el máximo posible.
Enfoque ingenuo: El enfoque del problema es:
Itere sobre todos los pares únicos en la array y encuentre el valor xor del triplete y realice un seguimiento del máximo.
Siga los pasos mencionados a continuación para implementar la idea anterior:
- Utilice dos bucles anidados para generar todos los pares únicos.
- Encuentre el xor de cada triplete arr[i] ⊕ arr[j] ⊕ K .
- Encuentre el máximo de xor para cada par.
- Al final devuelve el valor xor máximo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum Xor
int maxXor(vector<int>& v, int k)
{
// Here ans will store the maximum xor
// value possible of the triplet
int n = v.size(), ans = 0;
// We will try for all (n*(n+1))/2 pairs.
// And maximize the 'ans'.
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
ans = max(ans, v[i] ^ v[j] ^ k);
}
}
return ans;
}
// Driver Code
int main()
{
int N = 3, K = 2;
vector<int> arr = { 1, 2, 3 };
// Function call
cout << maxXor(arr, K);
return 0;
}
Java
// JAVA code to implement the approach
import java.util.*;
class GFG {
// Function to find the maximum Xor
public static int maxXor(int v[], int k)
{
// Here ans will store the maximum xor
// value possible of the triplet
int n = v.length, ans = 0;
// We will try for all (n*(n+1))/2 pairs.
// And maximize the 'ans'.
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
ans = Math.max(ans, v[i] ^ v[j] ^ k);
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 3, K = 2;
int[] arr = new int[] { 1, 2, 3 };
// Function call
System.out.print(maxXor(arr, K));
}
}
// This code is contributed by Taranpreet
Python3
# Python code to implement the approach # Function to find the maximum Xor def maxXor(v, k): # Here ans will store the maximum xor # value possible of the triplet n, ans = len(v), 0 # We will try for all (n*(n+1))/2 pairs. # And maximize the 'ans'. for i in range(n): for j in range(i, n): ans = max(ans, v[i] ^ v[j] ^ k) return ans # Driver Code N, K = 3, 2 arr = [ 1, 2, 3 ] # Function call print(maxXor(arr, K)) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
class GFG
{
// Function to find the maximum Xor
static int maxXor(int[] v, int k)
{
// Here ans will store the maximum xor
// value possible of the triplet
int n = v.Length, ans = 0;
// We will try for all (n*(n+1))/2 pairs.
// And maximize the 'ans'.
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
ans = Math.Max(ans, v[i] ^ v[j] ^ k);
}
}
return ans;
}
// Driver Code
public static void Main()
{
int N = 3, K = 2;
int[] arr = { 1, 2, 3 };
// Function call
Console.Write(maxXor(arr, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum Xor
function maxXor(v, k) {
// Here ans will store the maximum xor
// value possible of the triplet
let n = v.length, ans = 0;
// We will try for all (n*(n+1))/2 pairs.
// And maximize the 'ans'.
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
ans = Math.max(ans, v[i] ^ v[j] ^ k);
}
}
return ans;
}
// Driver Code
let N = 3, K = 2;
let arr = [1, 2, 3];
// Function call
document.write(maxXor(arr, K));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N * N)
Espacio auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando la estructura de datos Trie basada en la siguiente idea:
- Para maximizar el xor del triplete iterar sobre todos los elementos considerándolos como el segundo elemento . y elegir el tercer elemento eficientemente de tal manera que el xor del triplete sea el máximo posible.
- Maximice el XOR eligiendo los otros elementos de tal manera que el bit resultante sea 1 la mayor parte del tiempo, y dé prioridad primero al MSB y luego al LSB porque la contribución del MSB siempre es mayor que el LSB en el valor decimal final.
- Para ello, atravesaremos del MSB al LSB y si el bit está activado entonces buscaremos el 0 para que el bit resultante sea 1 y viceversa .
- Utilice la estructura de datos Trie . Porque para maximizar el valor de xor, necesitamos hacer la búsqueda de prefijos para el complemento de ese número , lo que se puede hacer de manera eficiente usando trie .
Siga los pasos a continuación para resolver este problema:
- En primer lugar, agregue todos los elementos al trie .
- Cada bit en un número tiene 2 posibilidades: 0 y 1 , por lo tanto, tenemos 2 punteros en cada Trie Node:
- child[0] -> apuntando a 0 bit &
- child[1] -> apuntando a 1 bit.
- Ahora inserte todos los elementos en el trie.
- Utilice un conjunto de bits de tamaño 32 ( bitset<32> B ) y pase del bit más significativo (MSB) al bit menos significativo (LSB).
- Ahora comience en la raíz de Trie y verifique si child[0] o child[1] está presente (no NULL), dependiendo del bit actual B[j] ( j varía de 0 al bit de número total) del número .
- Si está presente, vaya a su hijo, si no, cree un nuevo Node en ese hijo ( 0 bit o 1 bit) y muévase a su hijo.
- Ahora recorra la array y considere cada elemento como el segundo elemento elegido .
- Hasta ahora, el valor XOR actual del triplete es K ^ arr[i] .
- Ahora encuentre el tercer elemento usando trie tal que su xor con el xor actual sea máximo.
- Comience en la raíz del Trie y en el MSB del número (inicialice ans = 0 para almacenar la respuesta).
- Si el bit actual está configurado en el xor actual, vaya a child[0] para verificar si no es NULL.
- Si no es NULL, agregue 2 i-1 a ans (porque este bit se establecerá en la respuesta), de lo contrario, vaya a child[1] .
- Si no está configurado, vaya a child[1] para ver que no es NULL.
- Si no es NULL, agregamos 2 i-1 a ans, de lo contrario vamos a child[0] .
- Encuentre el máximo (digamos maxi ) entre el máximo xor posible en cada índice.
- Devuelve maxi como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Class for trie data structure
class TrieNode {
public:
TrieNode* child[2];
TrieNode()
{
// For '0' bit.
this->child[0] = NULL;
// For '1' bit.
this->child[1] = NULL;
}
};
TrieNode* newNode;
// Function toinsert the elements in trie
void insert(int x)
{
TrieNode* t = newNode;
// Convert x to bitwise representation
bitset<32> bs(x);
// Start from the MSB and
// move towards the LSB
for (int j = 30; j >= 0; j--) {
if (!t->child[bs[j]]) {
t->child[bs[j]]
= new TrieNode();
}
t = t->child[bs[j]];
}
}
// Function to return the max XOR of
// any element x with K
int findMaxXor(int k)
{
TrieNode* t = newNode;
bitset<32> bs(k);
// Here 'ans' will store the maximum
// possible xor corresponding to 'k'
int ans = 0;
for (int j = 30; j >= 0; j--) {
// For set bit we go to the bit
// '0' and for the bit '0' go
// towards '1', if available
if (t->child[!bs[j]]) {
ans += (1 << j), t = t->child[!bs[j]];
}
else {
t = t->child[bs[j]];
}
}
return ans;
}
// Function to find maximum possible xor
int maxXor(vector<int>& v, int K)
{
int n = v.size();
newNode = new TrieNode();
// Insert all the nodes
for (int i = 0; i < n; i++) {
insert(v[i]);
}
// Here 'ans' will store the maximum
// possible xor value of the triplet
int ans = 0;
// Try for every option, considering
// them as the second element
for (int i = 0; i < n; i++) {
ans = max(ans, findMaxXor(v[i] ^ K));
}
return ans;
}
// Driver code
int main()
{
int N = 3, K = 2;
vector<int> arr = { 1, 2, 3 };
// Function call
cout << maxXor(arr, K);
return 0;
}
Producción
3
Complejidad de tiempo: O(N * logM) donde M es el elemento máximo de la array.
Espacio Auxiliar: O(logM)