Dos elementos en la matriz cuyo xor es máximo

Question

Dado un conjunto de enteros, debe encontrar dos elementos cuyo XOR sea máximo.

Hay un enfoque ingenuo, simplemente seleccionando cada elemento y haciendo referencia a otros elementos y luego comparando los resultados para encontrar el par.

Aparte de esto, ¿hay algún algoritmo eficiente?

Answer 1

Creo que tengo un algoritmo O (n lg U) para esto, donde U es el número más grande. La idea es similar a la de user949300, pero con un poco más de detalle.

La intuición es la siguiente.Cuando está XORingando dos números juntos, para obtener el valor máximo, quiere tener un 1 en la posición más alta posible, y luego de los emparejamientos que tienen un 1 en esta posición, quiere un emparejamiento con un 1 en la siguiente Posible posición más alta, etc.

El algoritmo es el siguiente. Comience encontrando el más alto 1 bit en cualquier parte de los números (puede hacer esto en el tiempo O (n lg U) haciendo O (lg U) trabajo por cada uno de los n números). Ahora, divide el conjunto en dos partes: uno de los números que tienen un 1 en ese bit y el grupo con 0 en ese bit. Cualquier solución óptima debe combinar un número con un 1 en el primer punto con un número con un 0 en ese punto, ya que eso pondría un 1 bit lo más alto posible. Cualquier otro emparejamiento tiene un 0 allí.

Ahora, recursivamente, queremos encontrar el emparejamiento de números del grupo 1 y 0 que tiene el 1 más alto en ellos. Para ello, de estos dos grupos, divididos en cuatro grupos:

• números que empiezan con 11
• números que empiezan con 10
• números que empiezan con 01
• números que empiecen por 00

Si hay números en el grupo 11 y 00 o en los grupos 10 y 01, su XOR sería ideal (comenzando con 11). En consecuencia, si alguno de esos pares de grupos no está vacío, recursivamente calcule la solución ideal de esos grupos, luego devuelva el máximo de esas soluciones de subproblemas. De lo contrario, si ambos grupos están vacíos, esto significa que todos los números deben tener el mismo dígito en su segunda posición. En consecuencia, el XOR óptimo de un número que comienza con 1 y un número que comienza con 0 terminará teniendo el siguiente segundo bit cancelado, por lo que deberíamos simplemente mirar el tercer bit.

Esto da el siguiente algoritmo recursivo que, a partir de los dos grupos de números particionadas por su MSB, da la respuesta:

• Dada grupo 1 y grupo 0 y un índice de bit i:
  • Si el índice de bit es igual al número de bits, devuelva el XOR del número (único) en el grupo 1 y el número (único) en el grupo 0.
  • Construya los grupos 11, 10, 01 y 00 de esos grupos.
  • Si el grupo 11 y el grupo 00 no son vacíos, recursivamente encuentre el XOR máximo de esos dos grupos comenzando en el bit i + 1.
  • Si el grupo 10 y el grupo 01 son no vacíos, recursivamente encuentre el XOR máximo de esos dos grupos, comenzando en el bit i + 1.
  • Si cualquiera de los pares anteriores fue posible, devuelva el par máximo encontrado por la recursión.
  • De lo contrario, todos los números deben tener el mismo bit en la posición i, así devolver el par máximo encontrado examinado bit i + 1 en los grupos 1 y 0.

de comenzar el algoritmo, puede simplemente dividir los números del grupo inicial en dos grupos: números con MSB 1 y números con MSB 0. A continuación, ejecute una llamada recursiva al algoritmo anterior con los dos grupos de números.

Como ejemplo, considere los números 5 1 4 3 0 2.Estos tienen representaciones

101 001 100 011 000 010 

Comenzamos de dividir en el grupo 1 y el grupo 0:

101 100 
001 011 000 010 

Ahora, aplicamos el algoritmo anterior. Dividimos esta en grupos de 11, 10, 01, y 00:

11: 
10: 101 100 
01: 011 010 
00: 000 001 

Ahora, no podemos emparejar cualquier 11 elementos con 00 elementos, por lo que sólo recursivo de los grupos 10 y 01. Esto significa que construimos los 100, 101, 010, y 011 grupos:

101: 101 
100: 100 
011: 011 
010: 010 

Ahora que estamos abajo a cubos con sólo un elemento en ellos, sólo podemos comprobar los pares 101 y 010 (que da 111) y 100 y 011 (que da 111). Cualquiera de las opciones funciona aquí, por lo que obtenemos que la respuesta óptima es 7.

Pensemos en el tiempo de ejecución de este algoritmo. Observe que la profundidad máxima de recursión es O (lg U), ya que solo hay bits O (log U) en los números. En cada nivel del árbol, cada número aparece en exactamente una llamada recursiva, y cada una de las llamadas recursivas funciona proporcionalmente a la cantidad total de números en los grupos 0 y 1, porque necesitamos distribuirlos por sus bits. En consecuencia, hay niveles O (log U) en el árbol de recursión, y cada nivel funciona O (n), dando un trabajo total de O (n log U).

Espero que esto ayude! ¡Este fue un gran problema!

Answer 2

Ignorando el bit de signo, uno de los valores debe ser uno de los valores con el bit más alto establecido. A menos que todos los valores tengan ese bit establecido, en cuyo caso se pasa al siguiente bit significativo más alto que no está establecido en todos los valores. Entonces, puede reducir las posibilidades del primer valor mirando el HSB. Por ejemplo, si las posibilidades son

0x100000 
0x100ABC 
0x001ABC 
0x000ABC 

El primer valor del par máximo debe ser 0x100000 o 0x10ABCD.

@internal Server Error No creo que el más pequeño sea necesariamente correcto. No tengo una buena idea para reducir el 2do valor. Cualquier valor que no sea en la lista de posibles 1er. Valor. En mi ejemplo, 0x001ABC o 0x000ABC.

Answer 3

Realiza una función recursiva que toma dos listas de enteros, A y B, como sus argumentos. Como su valor de retorno, devuelve dos enteros, uno de A y otro de B, que maximizan el XOR de los dos. Si todos los enteros son 0, devuelve (0,0). De lo contrario, la función realiza algún procesamiento y se llama recursivamente dos veces, pero con enteros más pequeños. En una de las llamadas recursivas, considera tomar un número entero de la lista A para proporcionar un 1 a bit k, y en la otra llamada considera tomar un número entero de la lista B para suministrar un 1 a un bit k.

No tengo tiempo ahora para completar los detalles, pero tal vez esto sea suficiente para ver la respuesta? Además, no estoy seguro de si el tiempo de ejecución será mejor que N^2, pero probablemente lo será.

Answer 4

¡Un problema muy interesante! Aquí es mi idea:

• En primer lugar construir un árbol binario de todos los números mediante el uso de la representación binaria y clasificarlos en el árbol bit más significativo primero (añadir ceros a la izquierda para que coincida con el número más largo). Cuando se realiza cada ruta desde la raíz a cualquier hoja, representa un número del conjunto original .
• Deje ayb ser punteros a un nodo de árbol e inicializarlos en la raíz.
• Ahora mueva ayb por el árbol, tratando de usar bordes opuestos en cada paso, es decir, si a se mueve hacia abajo en un borde 0, b se mueve hacia abajo un borde a menos que no sea posible.

Si a y b alcanzan una hoja, deben señalar dos números con "muy pocos" bits idénticos.

Acabo de hacer este algoritmo y no sé si es correcto o cómo demostrarlo. Sin embargo, debería estar en O (n) tiempo de ejecución.

Answer 5

Podemos encontrar el número máximo en O (n) tiempo y luego recorrer el conjunto haciendo xor con cada elemento. Suponiendo que el costo de operación xor es O (1) podemos encontrar max xor de dos números en O (n) tiempo.

Answer 6

Esto se puede resolver en O(NlogN) complejidad de tiempo usando Trie.

• Construct a trie. Para cada clave entera, cada nodo del trie mantendrá cada bit (0 o 1) comenzando desde el bit más significativo.
• Ahora, para cada elemento de arr[i]arr[0, 1, ..... N]
  • Realizar consulta para recuperar el valor máximo posible para xor arr[i]. Sabemos que xor de diferentes tipos de bits (0^1 o 1^0) siempre es 1. Por lo tanto, durante la consulta de cada bit, intente atravesar el nodo que contiene el bit opuesto. Esto hará que ese bit en particular 1 resulte en la maximización de xor value. Si no hay ningún nodo con el bit opuesto, solo atraviesa el mismo nodo de bit.
  • Después de la consulta, inserte arr[i] en trie.
  • Para cada elemento, realice un seguimiento del valor Xor máximo posible.
  • Al recorrer cada nodo, construya la otra clave para la cual se maximiza Xor.

Para N elementos, que necesitan una consulta (O(logN)) y una inserción (O(logN)) para cada elemento. Entonces la complejidad general del tiempo es O(NlogN).

Puede encontrar una bonita explicación gráfica sobre cómo funciona in this thread.

Aquí es C aplicación ++ del algoritmo anterior:

const static int SIZE = 2; 
const static int MSB = 30; 
class trie { 
private: 
    struct trieNode { 
     trieNode* children[SIZE]; 
     trieNode() { 
      for(int i = 0; i < SIZE; ++i) { 
       children[i] = nullptr; 
      } 
     } 
     ~trieNode() { 
      for(int i = 0; i < SIZE; ++i) { 
       delete children[i]; 
       children[i] = nullptr; 
      } 
     } 
    }; 
    trieNode* root; 
public: 
    trie(): root(new trieNode()) { 
    } 
    ~trie() { 
     delete root; 
     root = nullptr; 
    } 

    void insert(int key) { 
     trieNode* pCrawl = root; 
     for(int i = MSB; i >= 0; --i) { 
      bool bit = (bool)(key & (1 << i)); 
      if(!pCrawl->children[bit]) { 
       pCrawl->children[bit] = new trieNode(); 
      } 
      pCrawl = pCrawl->children[bit]; 
     } 
    } 

    int query(int key, int& otherKey) { 
     int Xor = 0; 
     trieNode *pCrawl = root; 
     for(int i = MSB; i >= 0; --i) { 
      bool bit = (bool)(key & (1 << i)); 
      if(pCrawl->children[!bit]) { 
       pCrawl = pCrawl->children[!bit]; 
       Xor |= (1 << i); 
       if(!bit) { 
        otherKey |= (1 << i); 
       } else { 
        otherKey &= ~(1 << i); 
       } 
      } else { 
       if(bit) { 
        otherKey |= (1 << i); 
       } else { 
        otherKey &= ~(1 << i); 
       } 
       pCrawl = pCrawl->children[bit]; 
      } 
     } 
     return Xor; 
    } 
}; 

pair<int, int> findMaximumXorElements(vector<int>& arr) { 
    int n = arr.size(); 
    int maxXor = 0; 
    pair<int, int> result; 
    if(n < 2) return result; 
    trie* Trie = new trie(); 
    Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse 
    for(int i = 0; i < n; i++) { 
     int elem = 0; 
     int curr = Trie->query(arr[i], elem); 
     if(curr > maxXor) { 
      maxXor = curr; 
      result = {arr[i], elem}; 
     } 
     Trie->insert(arr[i]); 
    } 
    delete Trie; 
    return result; 
}