arrays - Dos elementos en matriz cuyo xor es máximo

algorithm bit-manipulation

Question

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

Se trata de 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

¡Un problema muy interesante! Aquí está mi idea:

• Primero construya un árbol binario a partir de todos los números mediante el uso de la representación binaria y ordénelos primero en el árbol del bit más significativo (agregue ceros a la izquierda para que coincida con el número más largo). Cuando haya terminado, 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 aa y b hacia abajo del á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 crear 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 2

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.

Entonces 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 hacer esto, de estos dos grupos, divídalos en cuatro grupos:

• Números que comienzan con 11
• Números que comienzan con 10
• Números que comienzan con 01
• Números que comienzan con 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 proporciona el siguiente algoritmo recursivo que, comenzando con los dos grupos de números particionados por su MSB, da la respuesta:

• Dado el grupo 1 y el 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 son no 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 emparejamientos anteriores fuera 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í que devuelve el par máximo encontrado mirando el bit i + 1 en los grupos 1 y 0.

Para comenzar el algoritmo, puede 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 dividiéndolos en el grupo 1 y el grupo 0:

101  100
001  011  000  010

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

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

Ahora, no podemos emparejar 11 elementos con 00 elementos, por lo que solo recursemos en los grupos 10 y 01. Esto significa que construimos los grupos 100, 101, 010 y 011:

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

Ahora que tenemos problemas con solo un elemento en ellos, podemos simplemente verificar 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 3

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

• Construye un 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 arr[i] de arr[0, 1, ..... N]
  • Realice una consulta para recuperar el valor xor máximo posible para arr[i] . Sabemos que xor de diferentes tipos de bits ( 0 ^ 1 o 1 ^ 0 ) es siempre 1 . Por lo tanto, durante la consulta de cada bit, intente atravesar el nodo que contiene el bit opuesto. Esto hará que ese bit 1 particular 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 caminar por cada nodo, construya la otra clave para la cual se maximiza Xor.

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

Puedes encontrar una bonita explicación pictórica sobre cómo funciona en este hilo .

Aquí está la implementación C ++ 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;
}

Answer 4

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.

@ error interno del servidor 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 esté en la lista de posibles 1er. Valor. En mi ejemplo, 0x001ABC o 0x000ABC.

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

Realice una función recursiva que tome 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á.