CODEWITHSUNDEEP
pythonalgorithmsortingbit-manipulationxor
Sam Si
Sam Si

Reputation: 333

Minimum XOR for queries

I was asked the following question in an interview.

Given an array A with N elements and an array B with M elements. For each B[X] return A[I] where XOR of A[I] and B[X] is minimum.

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 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 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:
        number_trie.add(val)

    ans = []

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

    return ans

Upvotes: 2

Views: 440

Answers (1)

user3386109
user3386109

Reputation: 34839

The key concept is that the XOR is minimized by matching as many of the most-significant bits as possible. For example, consider B[x] = 4, when the values in A are

1  0001
2  0010
3  0011
6  0110
9  1001

The binary pattern for 4 is 0100. So we're looking for a number that starts with 0. This eliminates the 9, since 9 has a 1 as the most-significant bit. Next, we're looking for a 1 in the second bit. Only 6 starts with 01, so 6 is the best match for 4.

To solve the problem efficiently, I would put the elements of A into a trie.

Using the example from the question, the trie would look something like this. (Note that it's possible to save memory and improve speed by allowing leaf nodes higher in the trie, but that complicates construction of the trie.)

enter image description here

Once the tree is constructed, it's easy to look up the answer for any B[x]. Just follow the bit pattern starting from the root. For nodes that have two children, go to the child that matches the current bit. For nodes with one child, there's no choice, so go to that child. When a leaf is found, that's the answer.

The run time is O(k(N+M)) where k is the number of bits in the largest number in A.
In the example, k is 4.

Upvotes: 4

Related Questions