CODEWITHSUNDEEP
arraysalgorithmcombinatoricsxor
Mark
Mark

Reputation: 139

Finding N elements in array whoes xor equals P

I am working on a problem in which I am expected to find the number of combinations of N<20 elements in array whose XOR equals P.

For example: our array is {2 4 5 2 7}

1) if N=2 and P=6,

The answer is 2 (as we can choose only (2 xor 4) = 6 and (4 xor 2) = 6)

{2 4 5 2 7} or {2 4 5 2 7}

2) if N=3 and P=6

The answer is 1 ((4 xor 5 xor 7) = 6)

The size of array can be really huge (something about 10^6) so I am looking for fast algorithm to solve that problem.

Upvotes: 13

Views: 848

Answers (2)

Valentin Waeselynck
Valentin Waeselynck

Reputation: 6061

Proposed recursive algorithm, may be faster than brute force:

Find some bit of P which is 1. Any solution combination must contain at least one number which has a 1 in that bit.

For each element K of the array which has a 1 at that bit, recur with:

  • P' = P xor K (xor - substraction)
  • arr' = arr - {set of J in arr which have a 1 in that bit, and which index is less than or equal to K} (because we're assuming K is the first element of the combination with a 1 at this position in the solution space)
  • N = N - 1

Termination cases:

  • if P=0, and N=0, one solution
  • if N=0 and P!=0, no solution
  • if arr is empty, no solution
  • if there's a bit where P has a 1 and no element of arr does, no solution

Note that XOR is associative and commutative, so we're counting sets, not combinations.

Upvotes: 0

Valentin Waeselynck
Valentin Waeselynck

Reputation: 6061

EDIT not working because N is fixed

Using linear algebra:

As suggested by @blazs, you can view P and each number of your array as vectors in a Z/2Z vector space. What's more, since XOR is associative and commutative, you're not looking for combinations of elements of your array, but sets of these elements, and a set can also be encoded as a Z/2Z vector.

So you'll end up with a matrix equation like M*S=P, where P is the xor-sum in Z/2Z vector format, M is the matrix which columns are the elements of the array in Z/2Z format , and S is the unknown of the equation.

Since you're only interested in the size of the solution space, all you need to do is find the dimension of the solution space, and then raise 2 to the power of it.

Upvotes: 1

Related Questions