# 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
2 ⊕ 5 = 7  <----- Max XOR
2 ⊕ 1 = 3
2 ⊕ 7 = 5
2 ⊕ 4 = 6
2 ⊕ 3 = 1
*/

/* queries
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); 