Maximum XOR problem

In this problem we need to find the maximum XOR between 2 elements of 2 arrays.

Example:

javascript
let array   = [5, 1, 7, 4, 3];
let queries = [2, 0];

/* queries[0]
2 ⊕ 5 = 7  <----- Max XOR
2 ⊕ 1 = 3
2 ⊕ 7 = 5
2 ⊕ 4 = 6
2 ⊕ 3 = 1
*/

/* queries[1]
0 ⊕ 5 = 5 
0 ⊕ 1 = 1
0 ⊕ 7 = 7  <----- Max XOR
0 ⊕ 4 = 4
0 ⊕ 3 = 3 
*/

/* res = [7, 7] */

The first approach is to iterate both arrays, calculating the maximum XOR for each pair of elements. The problem of this solution is that it's O(n · m) and not efficient.

The second approach is to notice that:

maxXOR = binary ⊕ inverse

Example:

javascript
let binary  = '101'; // 5
let inverse = '010'; // 2

let maxXor  = binary ^ inverse; // 111 -> 7

Solution summary

Given two arrays, array and queries:

1. Create a tree using array values.
2. Iterate queries and, for each value, find the closest inverse in the tree.
3. Apply maxXor = binary ⊕ closest

Creating the tree

At first, we'll create a tree using array.

Example:

javascript
let array  = [5, 1, 7, 4, 3];
let binary = ['101', '001', '111', '100', '011'];

The tree allows to perform a quick search of the closest inverse values that we are looking for.

terminal
           root
         /      \
        /        \
       /          \
      0            1
     /\           / \
    /  \         /   \
  00   01       10   11
   \     \      /\     \
    \     \    /  \     \
    001  011 100 101   111 

Translating it into code:

javascript
// Defining empty tree
let tree = {};

// Defining empty branch
let branch = '';

for(let i = 0; i < array.length; i ++){
    
    // Getting decimal
    let decimal = array[i];
    
    // Defining a 32-bits empty string
    let empty = ('0').repeat(32);
    
    // Transforming decimal into 32-bits binary
    let binary = (empty + decimal.toString(2)).slice(-32);
    
    // Iterating through 32-bits binary
    for(let j = 0; j < binary.length; j ++){
        
        // Adding one bit to current branch
        branch += binary[j];
        
        // Defining branch as empty object
        tree[branch] = {};
        
        // Adding 0 and 1 to left and right branches
        if(branch !== binary){
            
            if(binary[j + 1] === '0') tree[branch].left  = branch + '0';
            if(binary[j + 1] === '1') tree[branch].right = branch + '1'; 
            
        }    
        
    }
    
    // Resetting branch
    branch = '';
    
}

Find closest inverse of query values

Now, we need to find the closest inverse value for each query.

javascript
// Defining closest value
let closest = '';

// Defining array of max XOR's
let res = [];

for(let i = 0; i < queries.length; i ++){
    
    // Getting decimal
    let decimal = queries[i];
    
    // Defining a 32-bits empty string
    let empty = ('0').repeat(32);
    
    // Transforming decimal into 32-bits binary
    let binary = (empty + decimal.toString(2)).slice(-32);
    
    for(let j = 0; j < binary.length; j ++){
        
        // Getting current bit and inverting it
        let current = binary[j];
        let inverse = binary[j] === '1' ? '0' : '1';
        
        // Update closest value depending on the tree
        if(tree[closest + inverse]) closest += inverse;
        else                        closest += current;
    }
     
    // Defining max
    // maxXor = binary ⊕ closest`
    let maxXor = parseInt(binary, 2) ^ parseInt(closest, 2);

    // Adding to result
    res.push(maxXor);
    
    // Resetting closest value
    closest = '';
    
}

And that's it!