Minimum XOR for queries

I was asked the following question in an interview.

Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \otimes b$ is minimum, where $x\otimes y$ for to integers $x$ and $y$ is the bitwise xor operation of $x$ and $y$.

For example:

Input:

A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]

Output

[6, 9, 6, 9]

Because when 4 is XORed with any element in A minimum value will occur when A[I] = 6

4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5

Here is my brute force solution in python.

def get_min_xor(A, B):

    ans = []

    for val_b in B:
        min_xor = val_b ^ A[0]

        for val_a in A:
            min_xor = min(min_xor, val_b ^ val_a)
            # print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))

        ans.append(min_xor ^ val_b)

    return ans

Any ideas on how this could be solved in sub O(MxN) time complexity?

I had the following idea in mind.
I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B[X] would fit at ith position in A then I would check the min XOR of B[X] ^ A[i-1] and B[X] ^ A[i+1]. But this approach won't work in all the cases. For example the following input

A = [1,2,3]
B = [2, 5, 8]

Output:

[2, 1, 1]

Here is the trie based solution

```
class trie(object):
head = {}

def convert_number(self, number):
return format(number, '#032b')

def add(self, number):
cur_dict = self.head

binary_number = self.convert_number(number)

for bit in binary_number:

if bit not in cur_dict:
cur_dict[bit] = {}
cur_dict = cur_dict[bit]

cur_dict[number] = True

def search(self, number):
cur_dict = self.head

binary_number = self.convert_number(number)

for bit in binary_number:
if bit

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).

Let say we know that all integers in $A$ are 32-bit values. Use the following steps:

• Create an empty trie. Every node of trie may contains at most two children

for 0 and 1 bits.

• Insert all values in $A$ into the tree in $O(32 \times m) = O(m)$

• For each value in $B$, traverse the tree from the leftmost bit. If a bit doesn't match with child of a middle node, continue the traverse using the existing child until you reach a leaf. Traversing finishes in $O(32 \times n) = O(n)$

Which in total, the complexity is $O(m + n)$.

StackExchange Computer Science Q#118032, answer score: 6