3
$\begingroup$

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 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
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – narek Bojikian Dec 4 '19 at 1:29
  • 2
    $\begingroup$ 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. $\endgroup$ – Sam Si Dec 4 '19 at 6:39
-2
$\begingroup$

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;
    }
}
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Mar 22 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.