Efficient way to find Xor of pairs with given target X in a range 0 to K

Question

I came across a problem: given an array (can be huge 10^8) and an integer, K, find the count of pairs in the array whose Xor equal to each value in the range 0 to K. eg:

 Arr = 1 2 3
 K = 2 

since K=2, possible values of x are 0, 1 or 2.

x = 0

• There are 0 pairs whose Xor=0.

x = 1

• There is 1 pair {2,3}, whose Xor=1.

x = 2

• There is 1 pair {1,3}, whose Xor=2.

So output is

0 1 1

I know an n² solution to this problem where I loop x from 0 to K and now used hashing over the array find all such pairs whose sum is equal to the current x add it to the result array.

I'm seeking a better approach.

Answer 1

Rainbow table

Unfortunately the work has to be done sometime, but if you have the space you can do a lot of that work once.

The Rainbow table is literally a computation table. Given X, Y, and the Op what is the result.

xor | 00 | 01 | 10 | 11 |
----|----|----|----|----|
 00 | 00 | 01 | 10 | 11 |
 01 | 01 | 00 | 11 | 10 |
 10 | 10 | 11 | 00 | 01 |
 11 | 11 | 10 | 01 | 00 |

Is the Rainbow table for any two bit integer.

Right off the bat you can see that the table is reflexive. (Which makes sense as xor is commutative.) So we only need to compute half the triangle.

xor | 00 | 01 | 10 | 11 |
----|----|----|----|----|
 00 | 00 |    |    |    |
 01 | 01 | 00 |    |    |
 10 | 10 | 11 | 00 |    |
 11 | 11 | 10 | 01 | 00 |

The next realisation is that 0 is a special case. Its pairs are always identical.

• If the elements in the array are unique then the output 0 will always have 0 pairs.
• If the elements are not unique, a simplified computation can be used that doesn't need the table. See lower.

Also notice that none of the other outputs ever have an identical pair. (otherwise it would be on that middle diagonal). That makes computation easier later.

xor | 00 | 01 | 10 |
----|----|----|----|
 01 | 01 |    |    |
 10 | 10 | 11 |    |
 11 | 11 | 10 | 01 |

But that isn't the most efficient representation for performing the later calculation on. What we want is a table of outputs and whether or not a given pair of inputs is in that set.

|  = 01 |  = 10 |  = 11 |
|-------|-------|-------|
| 01^00 | 10^00 | 11^00 |
| 11^10 | 11^01 | 10^01 |

Precomputing will take O(N^2).

Now to compute the pairs for a given array.

Preprocess the array by accumulating the elements into (element, tally) pairs, and ensuring elements are sorted, call this input. Op max runtime O(NlogN).

For Output = 0: sum (for each (element, tally): if (tally >= 2) tally!/(2(tally-2)!) else 0)

or more pseudo code

int tally = 0;
for each (element, e_tally) in input
{
  if (e_tally > 1)
    tally += ((e_tally * (e_tally-1)) >> 1);
}
return tally;

For Output > 0:

int tally = 0;
for each (a, b) in rainbow[output]
{
  if (input.has(a) && input.has(b))
     tally += (input[a]* input[b]);
}
return tally;

if the array is unique then, output > 0:

int tally = 0;
for each (a, b) in rainbow[output]
{
  if (input.has(a) && input.has(b))
     ++tally;
}
return tally;

The calculation time is O(N), presuming a presorted/preaccumulated array. O(NlogN) if that is not the case.

Given that XOR is a fairly regular function, you could potentially apply the same table iteratively on a byte by byte, or even short by short manner. This would slow down the algorithm by introducing another variable R which varies with the size of the integer, optimising for smaller R (smaller integers), while still having a small speed up on larger numbers.