0

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.

6
  • Is the array dense? And is K always the first K elements, or is an actual element chosen from the array? – Kain0_0 Sep 14 '20 at 5:35
  • @Kain0_0 yes array is dense, K is not the first element it can be anything from 0 to 10^5. eg " 1 5 3" K=6 here output will be "0 0 1 0 1 0 1" since {1,3} gives 2 {1,5} gives 4 {3,5} gives 6 when Xor is performed those are only possible sets. – Kalpish Singhal Sep 14 '20 at 6:32
  • You are probably not going to get his problem below N^2. You cannot attack it by swapping to a radix sort, as the prefix is important to the xoring and is dropped by that approach. Considering it as a graph, its a kind of hyper-cube which boils down to counting edges. You might have some luck investigating Group Theory, but that is a branch of mathematics which is beyond all but a simplistic understanding to me. – Kain0_0 Sep 14 '20 at 9:23
  • 1
    Try asking on the computer science board. – Kain0_0 Sep 14 '20 at 9:23
  • I'm thinking as xor is on a range some optimization like by memorization or segment tree can optimize it. – Kalpish Singhal Sep 14 '20 at 9:39
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.

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.