Dada una array arr[] que consta de N enteros no negativos y una array 2D queries[][] que consta de consultas del tipo {X, M} , la tarea de cada consulta es encontrar el XOR bit a bit máximo de X con cualquier elemento de array cuyo valor es como máximo M . Si no es posible encontrar el XOR bit a bit, imprima «-1» .
Ejemplos:
Entrada: arr[] = {0, 1, 2, 3, 4}, consultas[][] = {{3, 1}, {1, 3}, {5, 6}}
Salida: {3, 3, 7}
Explicación:
Consulta 1: La consulta es {3, 1}. Bitwise XOR máximo = 3 ^ 0 = 3.
Consulta 2: la consulta es {1, 3}. Bitwise XOR máximo = 1 ^ 2 = 3.
Consulta 3: la consulta es {5, 6}. XOR bit a bit máximo = 5 ^ 2 = 7.Entrada: arr[] = {5, 2, 4, 6, 6, 3}, consultas[][] = {{12, 4}, {8, 1}, {6, 3}}
Salida: {15, -15}
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es recorrer la array dada para cada consulta {X, M} e imprimir el valor máximo de Bitwise XOR de X con un elemento de array con un valor como máximo M . Si no existe ningún valor menor que M , imprima «-1» para la consulta.
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la estructura de datos Trie para almacenar todos los elementos que tengan valores como máximo M . Por lo tanto, el problema se reduce a encontrar el XOR máximo de dos elementos en una array . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos index , para recorrer la array .
- Inicialice una array, digamos ans[] , que almacene el resultado de cada consulta.
- Inicialice una array auxiliar, diga temp[][3] , y almacene todas las consultas en ella con el índice de cada consulta.
- Ordene la array dada temp[] sobre la base del segundo parámetro, es decir, temp[1] (= M ).
- Ordene la array dada arr[] en orden ascendente .
- Recorra la array temp[] y para cada consulta {X, M, idx} , realice los siguientes pasos:
- Iterar hasta que el valor de index sea menor que N y arr[index] sea como máximo M o no. Si se determina que es cierto, inserte ese Node como la representación binaria de N e incremente el índice .
- Después de completar los pasos anteriores, si el valor de index no es cero , busque el Node con el valor X en el Trie (digamos resultado ) y actualice el valor máximo para la consulta actual como resultado . De lo contrario, actualice el valor máximo para la consulta actual como «-1» .
- Después de completar los pasos anteriores, imprima la array ans[] como los valores máximos resultantes para cada consulta.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// Trie Node Class
class TrieNode {
TrieNode nums[] = new TrieNode[2];
int prefixValue;
}
class sol {
// Function to find the maximum XOR
// of X with any array element <= M
// for each query of the type {X, M}
public void maximizeXor(
int[] nums, int[][] queries)
{
int queriesLength = queries.length;
int[] ans = new int[queriesLength];
int[][] temp = new int[queriesLength][3];
// Stores the queries
for (int i = 0; i < queriesLength; i++) {
temp[i][0] = queries[i][0];
temp[i][1] = queries[i][1];
temp[i][2] = i;
}
// Sort the query
Arrays.sort(temp,
(a, b) -> {
return a[1]
- b[1];
});
int index = 0;
// Sort the array
Arrays.sort(nums);
TrieNode root = new TrieNode();
// Traverse the given query
for (int query[] : temp) {
// Traverse the array nums[]
while (index < nums.length
&& nums[index]
<= query[1]) {
// Insert the node into the Trie
insert(root, nums[index]);
index++;
}
// Stores the resultant
// maximum value
int tempAns = -1;
// Find the maximum value
if (index != 0) {
// Search the node in the Trie
tempAns = search(root,
query[0]);
}
// Update the result
// for each query
ans[query[2]] = tempAns;
}
// Print the answer
for (int num : ans) {
System.out.print(num + " ");
}
}
// Function to insert the
// root in the trieNode
public void insert(TrieNode root,
int n)
{
TrieNode node = root;
// Iterate from 31 to 0
for (int i = 31; i >= 0; i--) {
// Find the bit at i-th position
int bit = (n >> i) & 1;
if (node.nums[bit] == null) {
node.nums[bit]
= new TrieNode();
}
node = node.nums[bit];
}
// Update the value
node.prefixValue = n;
}
// Function to search the root
// with the value and perform
// the Bitwise XOR with N
public int search(TrieNode root,
int n)
{
TrieNode node = root;
// Iterate from 31 to 0
for (int i = 31; i >= 0; i--) {
// Find the bit at ith
// position
int bit = (n >> i) & 1;
int requiredBit = bit
== 1
? 0
: 1;
if (node.nums[requiredBit]
!= null) {
node = node.nums[requiredBit];
}
else {
node = node.nums[bit];
}
}
// Return the prefixvalue XORed
// with N
return node.prefixValue ^ n;
}
}
class GFG {
// Driver Code
public static void main(String[] args)
{
sol tt = new sol();
int[] nums = { 0, 1, 2, 3, 4 };
int[][] queries = { { 3, 1 },
{ 1, 3 },
{ 5, 6 } };
tt.maximizeXor(nums, queries);
}
}
3 3 7
Complejidad de tiempo: O(N*log N + K*log K)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA