Encuentre el XOR máximo de un entero dado en una secuencia de enteros

Se le da un número de consultas Q y cada consulta será de los siguientes tipos:

1. Consulta 1 : agregar (x) Esto significa agregar x en su estructura de datos.
2. Consulta 2 : maxXOR(y) Esto significa imprimir el máximo XOR posible de y con todos los elementos ya almacenados en la estructura de datos.

1 <= x, y <= 10^9
1 <= 10^5 <= Q
La estructura de datos comienza con solo un 0.

Ejemplo:

Input: (1 10), (1 13), (2 10), (1 9), (1 5), (2 6)
Output: 7 15

Add 10 and 13 to stream.
Find maximum XOR with 10, which is 7
Insert 9 and 5
Find maximum XOR with 6 which is 15.

Una buena manera de resolver este problema es usar un Trie. Un requisito previo para esta publicación es Trie Insert and Search .

Cada Trie Node tendrá el siguiente aspecto:

struct TrieNode
{
    // We use binary and hence we 
    // need only 2 children
    TrieNode* Children[2]; 
    bool isLeaf;
};

Otra cosa a manejar es que tenemos que rellenar el equivalente binario de cada número de entrada con un número adecuado de ceros a la izquierda antes de almacenarlos. El valor máximo posible de x o y es 10 ^ 9 y, por lo tanto, 32 bits serán suficientes.

Entonces, ¿cómo funciona esto?
Supongamos que tenemos que insertar 3 y 7 en Trie. El Trie comienza con 0 y después de estas tres inserciones se puede visualizar así:

Para simplificar, el relleno se ha realizado para almacenar cada número usando 3 bits. Tenga en cuenta que en binario:
3 es 011
7 es 111
Ahora, si tenemos que insertar 1 en nuestro Trie, podemos notar que 1 es 001 y ya tenemos la ruta para 00. Así que creamos un nuevo Node para el último bit establecido y después conectando, obtenemos esto:

Ahora si tenemos que tomar XOR con 5 que es 101, notamos que para el bit más a la izquierda (posición 2), podemos elegir un 0 comenzando en la raíz y así vamos a la izquierda. Esta es la posición 2 y sumamos 2^2 a la respuesta.
Para la posición 1, tenemos un 0 en 5 y vemos que podemos elegir un 1 de nuestro Node actual. Así vamos a la derecha y sumamos 2^1 a la respuesta.
Para la posición 0, tenemos un 1 en 5 y vemos que no podemos elegir un 0 de nuestro Node actual, por lo que vamos a la derecha.

The path taken for 5 is shown above. The answer is thus 2^2 + 2^1 = 6.

// C++ program to find maximum XOR in
// a stream of integers
#include<bits/stdc++.h>
using namespace std;
  
struct TrieNode
{
    TrieNode* children[2];
    bool isLeaf;
};
  
// This checks if the ith position in
// binary of N is a 1 or a 0
bool check(int N, int i)
{
    return (bool)(N & (1<<i));
}
  
// Create a new Trie node
TrieNode* newNode()
{
    TrieNode* temp = new TrieNode;
    temp->isLeaf = false;
    temp->children[0] = NULL;
    temp->children[1] = NULL;
    return temp;
}
  
// Inserts x into the Trie
void insert(TrieNode* root, int x)
{
    TrieNode* Crawler = root;
  
    // padding upto 32 bits
    for (int i = 31; i >= 0; i--)
    {
        int f = check(x, i);
        if (! Crawler->children[f])
            Crawler->children[f] = newNode();
        Crawler = Crawler->children[f];
    }
    Crawler->isLeaf = true;
}
  
// Finds maximum XOR of x with stream of
// elements so far.
int query2(TrieNode *root, int x)
{
    TrieNode* Crawler = root;
  
    // Do XOR from root to a leaf path
    int ans = 0;
    for (int i = 31; i >= 0; i--)
    {
        // Find i-th bit in x
        int f = check(x, i);
  
        // Move to the child whose XOR with f
        // is 1.
        if ((Crawler->children[f ^ 1]))
        {
            ans = ans + (1 << i); // update answer
            Crawler = Crawler->children[f ^ 1];
        }
  
        // If child with XOR 1 doesn't exist
        else
            Crawler = Crawler->children[f];
    }
  
    return ans;
}
  
// Process x (Add x to the stream)
void query1(TrieNode *root, int x)
{
    insert(root, x);
}
  
// Driver code
int main()
{
    TrieNode* root = newNode();
    query1(root, 10);
    query1(root, 13);
    cout << query2(root, 10) << endl;
    query1(root, 9);
    query1(root, 5);
    cout << query2(root, 6) << endl;
    return 0;
}

7
15

El espacio ocupado por el Trie es O(n*log(n)). Cada consulta de tipo 1 toma un tiempo O(log(n)). Cada consulta de tipo 2 también requiere tiempo O(log(n)). Aquí n es el número de consulta más grande.

Problema de seguimiento: ¿Qué pasa si nos dan tres consultas en lugar de dos?
1) agregar (x) Esto significa agregar x en su estructura de datos (se permiten duplicados).
2) maxXOR(y) Esto significa imprimir el máximo XOR posible de y con todos los elementos ya almacenados en la estructura de datos.
3) remove(z) Esto significa eliminar una instancia de z de la estructura de datos.
¿Qué cambios en la solución Trie pueden lograr esto?

Este artículo es una contribución de Hemang Sarkar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.