Due elementi nella matrice il cui xor è massimo

Question

Dato un array di numeri interi, Devi trovare due elementi il ​​cui XOR è massimo.

C'è un approccio ingenuo: basta selezionare ogni elemento e fare xorare con altri elementi e quindi confrontare i risultati per trovare la coppia.

Oltre a questo, esiste un algoritmo efficiente?

Answer 1

Penso di avere un algoritmo O (n Lg U) per questo, dove U è il numero più grande. L'idea è simile a quella di user949300, ma con qualche dettaglio in più.

L'intuizione è la seguente.Quando stai XORando due numeri insieme, per ottenere il valore massimo, vuoi avere un 1 nella posizione più alta possibile, e quindi degli abbinamenti che hanno un 1 in questa posizione, vuoi un abbinamento con un 1 alla successiva possibile posizione più alta, ecc.

Quindi l'algoritmo è il seguente. Iniziate trovando il massimo 1 bit in qualsiasi punto dei numeri (potete farlo nel tempo O (n lg U) eseguendo il lavoro O (lg U) per ciascuno dei n numeri). Ora, dividi l'array in due parti: uno dei numeri che hanno un 1 in quel bit e il gruppo con 0 in quel bit. Qualsiasi soluzione ottimale deve combinare un numero con un 1 nel primo punto con un numero con uno 0 in quel punto, poiché ciò metterebbe un 1 bit più alto possibile. Qualsiasi altro accoppiamento ha uno 0 lì.

Ora, in modo ricorsivo, vogliamo trovare l'accoppiamento di numeri dal gruppo 1 e 0 che ha il più alto 1 in essi. Per fare questo, di questi due gruppi, dividerle in quattro gruppi:

• numeri che iniziano con 11
• numeri che iniziano con 10
• numeri che iniziano con 01
• numeri che iniziano con 00

Se ci sono numeri nel gruppo 11 e 00 o nei gruppi 10 e 01, il loro XOR sarebbe ideale (iniziando con 11). Di conseguenza, se una di queste coppie di gruppi non è vuota, calcola ricorsivamente la soluzione ideale da quei gruppi, quindi restituisce il massimo di tali soluzioni per sottoproblemi. Altrimenti, se entrambi i gruppi sono vuoti, significa che tutti i numeri devono avere la stessa cifra nella loro seconda posizione. Di conseguenza, lo XOR ottimale di un numero che inizia con 1 e un numero che inizia con 0 finirà con l'annullamento del secondo bit successivo, quindi dovremmo solo guardare il terzo bit.

Questo dà il seguente algoritmo ricorsivo che, a partire dai due gruppi di numeri partizionata da loro MSB, dà la risposta:

• Dato gruppo 1 e gruppo 0 e un indice di bit i:
  • Se l'indice di bit è uguale al numero di bit, restituire lo XOR del numero (univoco) nel gruppo 1 e il numero (univoco) nel gruppo 0.
  • Costruisci i gruppi 11, 10, 01 e 00 da quei gruppi.
  • Se il gruppo 11 e il gruppo 00 sono non vuota, in modo ricorsivo trovare il XOR massimo di questi due gruppi a partire da po 'i + 1.
  • Se il gruppo 10 e il gruppo 01 sono non vuota, in modo ricorsivo trovare la XOR massimo di questi due gruppi, a partire dal bit i + 1.
  • Se uno degli accoppiamenti precedenti era possibile, restituire la coppia massima trovata dalla ricorsione.
  • In caso contrario, tutti i numeri devono avere lo stesso bit in posizione i, in modo da restituire la coppia massima trovato, cercando in bit i + 1 sui gruppi 1 e 0.

per iniziare la Algoritmo, puoi effettivamente suddividere i numeri dal gruppo iniziale in due gruppi: i numeri con MSB 1 e i numeri con MSB 0. Quindi fai una chiamata ricorsiva all'algoritmo sopra con i due gruppi di numeri.

Ad esempio, considerare i numeri 5 1 4 3 0 2.Questi hanno rappresentazioni

101 001 100 011 000 010 

Cominciamo, dividendoli in 1 gruppo e il gruppo 0:

101 100 
001 011 000 010 

Ora, applichiamo l'algoritmo di cui sopra. Ci siamo divisi in gruppi questo 11, 10, 01 e 00:

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

Ora, non possiamo abbinare ogni 11 elementi con 00 elementi, quindi abbiamo recurse sui gruppi 10 e 01. Ciò significa che costruire i 100, 101, 010, e 011 gruppi:

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

Ora che siamo giù a secchi con un solo elemento in esse, possiamo solo controllare le coppie di 101 e 010 (che dà 111) e 100 e 011 (che dà 111). Entrambe le opzioni funzionano qui, quindi la risposta ottimale è 7.

Pensiamo al tempo di esecuzione di questo algoritmo. Si noti che la profondità massima di ricorsione è O (lg U), poiché ci sono solo bit O (log U) nei numeri. Ad ogni livello dell'albero, ogni numero appare esattamente in una chiamata ricorsiva, e ciascuna delle chiamate ricorsive funziona in modo proporzionale al numero totale di numeri nei gruppi 0 e 1, perché è necessario distribuirli per i loro bit. Di conseguenza, ci sono livelli O (log U) nell'albero di ricorsione, e ogni livello fa O (n) funziona, dando un lavoro totale di O (n log U).

Spero che questo aiuti! Questo è stato un grosso problema!

Answer 2

Ignorando il bit di segno, uno dei valori deve essere uno dei valori con il bit significativo più alto impostato. A meno che tutti i valori non abbiano impostato quel bit, nel qual caso si passa al bit più significativo successivo che non è impostato su tutti i valori. Quindi potresti ridurre le possibilità del 1 ° valore guardando l'HSB. Ad esempio, se le possibilità sono

0x100000 
0x100ABC 
0x001ABC 
0x000ABC 

Il primo valore della coppia massima deve essere 0x100000 o 0x10ABCD.

@internal Errore del server Non penso che il più piccolo sia necessariamente corretto. Non ho una grande idea per ridurre il 2 ° valore. Qualsiasi valore che non sia nell'elenco di possibili 1 ° valori. Nel mio esempio, 0x001ABC o 0x000ABC.

Answer 3

Creare una funzione ricorsiva che utilizzi due elenchi di numeri interi, A e B, come argomenti. Come valore di ritorno, restituisce due interi, uno da A e uno da B, che massimizzano lo XOR dei due. Se tutti gli interi sono 0, restituisce (0,0). Altrimenti, la funzione esegue un po 'di elaborazione e si chiama in modo ricorsivo due volte, ma con numeri interi più piccoli. In una delle chiamate ricorsive, prende in considerazione l'assunzione di un intero dalla lista A per fornire da 1 a bit k, e nell'altra chiamata considera prendere un numero intero dalla lista B per fornire da 1 a bit k.

Non ho tempo ora di inserire i dettagli, ma forse questo sarà sufficiente per vedere la risposta? Inoltre, non sono sicuro che il tempo di esecuzione sarà migliore di N^2, ma probabilmente lo sarà.

Answer 4

Un problema molto interessante! Ecco la mia idea:

• prima costruire un albero binario da tutti i numeri utilizzando il file binario rappresentazione e ordinarli in l'albero bit più significativo prima (aggiungere zeri iniziali in base al numero di più lungo). Quando si esegue ogni percorso dalla radice a qualsiasi foglia rappresenta un numero dal set originale .
• Sia aeb sia i puntatori a un nodo di albero e inizializzati nella radice.
• Ora sposta a e b lungo l'albero, cercando di usare i bordi opposti ad ogni passo, cioè se si sposta verso il basso di un bordo 0, b si sposta verso il basso di un margine a meno che non sia possibile.

Se a e b raggiungono una foglia, il punto dovrebbe indicare due numeri con "pochissimi" bit identici.

Ho appena fatto questo algoritmo e non so se è corretto o come dimostrarlo. Tuttavia dovrebbe essere in O (n) tempo di esecuzione.

Answer 5

Possiamo trovare il numero massimo nel tempo O (n), quindi fare un ciclo attraverso l'array eseguendo xo ogni elemento. Supponendo che il costo dell'operazione xor sia O (1) possiamo trovare il massimo xor di due numeri nel tempo O (n).

Answer 6

Questo problema può essere risolto nella complessità temporale O(NlogN) utilizzando Trie.

• Costruire un trie. Per ogni chiave intera, ogni nodo del trie manterrà ogni bit (0 o 1) a partire dal bit più significativo.
• Ora, per ciascun elemento della arr[i]arr[0, 1, ..... N]
  • Eseguire query per recuperare il massimo valore possibile per XOR arr[i]. Sappiamo che xor di diversi tipi di bit (0^1 o 1^0) è sempre 1. Quindi durante la query per ogni bit, provare a attraversare il nodo tenendo il bit opposto. Ciò renderà quel particolare bit 1 il risultato di massimizzare il valore xor. Se non ci sono nodi con bit opposto, solo allora attraversare lo stesso nodo di bit.
  • Dopo la query, inserire arr[i] in trie.
  • Per ciascun elemento, tenere traccia del valore Xor massimo possibile.
  • Durante la navigazione attraverso ciascun nodo, creare l'altra chiave per la quale viene ingrandita la Xor.

Per N elementi, dobbiamo una query (O(logN)) e da un inserimento (O(logN)) per ogni elemento. Quindi la complessità del tempo complessivo è O(NlogN).

È possibile trovare una bella spiegazione pittorica su come funziona in this thread.

Ecco C implementazione ++ dell'algoritmo di cui sopra:

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; 
}