Finding pairs with smallest XOR values from a list

Question

I am working on a problem in which I am expected to take the xor of all the pair of integers in an array and then find the K smallest integers produced from xor'ing. The size of the array can be N=100000 and so K can be quite large but its limited to 250000.

For example, if N=5 and K=4,

our array is {1 3 2 4 2}

The numbers resulting from xoring(1 and 3, 1-2, 1-4, 1-2, 3-2, 3-4, 3-2 etc)

3 3 2 5 0 1 6 1 6 7

Since K=4, we have to print 4 smallest integers. so the answer would be 0 1 1 2.

Since the time limit is 2 sec and very tight, using the brute force approach of xoring all the numbers would time out. My approach was wrong and so I need help. May be we can exploit the limit on K=250000 and want to know if it is possible to get the K smallest numbers without xoring all the integers.

Answer 1

(x ^ y) == (x | y) - (x & y) >= |y - x|

Sorting your numbers in order would be a start, because the difference between the pairs will give you a lower bound for the xor, and therefore a cutoff point for when to stop looking for numbers to xor x with.

There is also a shortcut to looking for pairs of numbers whose xor is less than (say) a power of 2, because you're only interested in x <= y <= x | (2 ^ N - 1). If this doesn't give you enough pairs, increase N and try again.

EDIT: You can of course exclude the pairs of numbers that you already found whose xor is less than the previous power of 2, by using x | (2 ^ (N - 1) - 1) < y <= x | (2 ^ N) - 1.

Example based on (sorted) [1, 2, 2, 3, 4]

Start by looking for pairs of numbers whose xor is less than 1: for each number x, search for subsequent numbers y = x. This gives {2, 2}.

If you need more than one pair, look for pairs of numbers whose xor is less than 2 but not less than 1: for each number x, search for numbers x < y <= x | 1. This gives {2, 3} (twice).

Note that the final xor values aren't quite sorted, but each batch is strictly less than the previous batch.

If you need more than that, look for pairs of numbers whose xor is less than 4 but not less than 2: for each number x, search for numbers x | 1 < y <= x | 3. This gives {1, 2} (twice); {1, 3}.

If you need more than that, look for pairs of numbers whose xor is less than 8 but not less than 4: for each number x, search for numbers x | 3 < y <= x | 7. This gives {1, 4}; {2, 4} (twice); {3, 4}.

Answer 2

Notice that if the all bits to the left of bit n (counting from the right) of numbers x and y are equal, x xor y ≤ 2ⁿ-1

x = 0000000000100110
y = 0000000000110010
               ^Everything to the left of bit 5 is equal
                so x xor y ≤ 25-1 = 31

This can be exploited by storing every number in a bitwise-trie - that is, a trie where every edge is either a 0 or a 1. Then x xor y ≤ 2^d(x,y)-1, where d(x,y) is the number of steps we need to move up to find the least-common ancestor of x and y.

                             root
                        (left-most bit)
                              0
                             /
                            0
                           /
                          ...
                          1
                         / \
                        0   1
                       /   /
                      0   0
                    ... ...
                    /   /
                   0   0
                   x   y

x and y share an ancestor-node that is 5 levels up, so d(x,y) is 5

Once you have the trie, it's easy to find all pairs such that d(x,y) = 1 - just navigate to all nodes 1 level above the leaves, and compare each of that node's children to each other. Those values will give you a max x xor y of 2¹-1 = 1.

If you still don't have k values, then move up to all nodes 2 levels above the leaves, and compare each of that node's grandchildren to each other^†. Those values will give you a max x xor y of 2²-1 = 3.

^†(Actually, you only need to compare each of the leaves in the left-subtree with each of the leaves in the right-subtree, since each of the leaves in a given subtree have already been compared against each other)

Continue this until, after checking all nodes for a given level, you have at least k values of x xor y. Then sort that list of values, and take the k smallest.

---

When k is small (<< n²), this algorithm is O(n). For large k, it is O(2^bn), where b is the number of bits per integer (assuming there are not many duplicates).