# 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):

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

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):

binary_number = self.convert_number(number)

for bit in binary_number:
if bit not in cur_dict:
if bit == "1":
cur_dict = cur_dict["0"]
else:
cur_dict = cur_dict["1"]
else:
cur_dict = cur_dict[bit]

return list(cur_dict.keys())[0]

def get_min_xor_with_trie(A,B):

number_trie = trie()

for val in A:

ans = []

for val in B:
ans.append(number_trie.search(val))

return ans


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)$$.

• It would be nice to add a bit of explanation in the beginning of the answer, explaining what you are trying to achieve through the Trie and why the found element minimizes the answer. Describing an algorithm directly without giving a bit of context might sometimes be confusing. Dec 4, 2019 at 1:29
• Thank you for the approach. I will try to code this myself and will mark it as answer once I am done. As @narekBojikian mentioned intuition behind your approach is always welcome. Dec 4, 2019 at 6:39

Using Trie Data Structure.

public class Solution {

public int[] solve(int[] A, int[] B) {
int ans[] = new int[B.length];
Trie root = new Trie();
for (int s : A) {
insert(root, s);
}
for (int i = 0; i < B.length; i++) {
ans[i] = search(root, B[i]);
}
return ans;
}

class Trie {
public Trie left, right;
public int val;

public Trie() {
left = right = null;
val = Integer.MIN_VALUE;
}
}

public void insert(Trie t, int n) {
Trie root = t;
for (int pos = 31; pos >= 0; pos--) {
int bit = (1 << pos) & n;
if (bit == 0) {
if (t.left == null) {
t.left = new Trie();
}
t = t.left;
} else {
if (t.right == null)
t.right = new Trie();
t = t.right;
}
if (pos == 0)
t.val = n;

}
}

private int search(Trie t, int n) {
// TODO Auto-generated method stub
Trie root = t;
for (int pos = 31; pos >= 0; pos--) {
int bit = (1 << pos) & n;
if (bit == 0) {
if (t.left != null)
t = t.left;
else
t = t.right;

} else {
if (t.right != null)
t = t.right;
else
t = t.left;
}
if (pos == 0)
return t.val;
}
return 0;
}
}

• We're not a coding side, and we're not looking for code-only answers. Instead, we're looking for ideas, concise pseudocode, explanations, etc.
– D.W.
Mar 22, 2020 at 19:09