CODEWITHSUNDEEP
arraysalgorithmsubsetlinear-algebra
Bijan
Bijan

Reputation: 139

How do you find the largest subset of an array of integers that xor to zero

To clarify, the largest subset of the array: [0,1,4,5,6,8] that xors to 0 would be [0,1,4,5] since 0^1^4^5=0 (where ^ is xor). I know this can be done in exponential time by brute force, but I'd like to know what the lower bound is, and what algorithm solves it in that time.

I'm doing to implement the Rational sieve algorithm. Beyond the wikipedia article, resources on the algorithm are fairly scarce. To complete the rational sieve you attempt to find a subset of a group of arrays, such that when adding up corresponding elements, the resulting array has only even numbers. For example:

[2,3,4,5]+[4,3,4,3]=[6,6,8,8] This would be a valid solution, provided that these arrays exist in the larger set.

According to that wikipedia article, this can be solved using linear algebra, but I don't know enough linear algebra to solve it.

For the purpose of the algorithm, an empty subset isn't useful.

I simplified the problem by saying that the arrays can only have 0s, and 1s, and by putting the array into a single number so that the sum can be computed with a single operator, but otherwise they are the same problem.

Upvotes: 3

Views: 373

Answers (1)

Rafał Dowgird
Rafał Dowgird

Reputation: 45131

Yes, it can be formulated as a linear optimization problem. Assuming the integers are k bits and there are n of them, you can represent them as a k * n matrix A, where columns represent the integers, and row r of column n is the r-th bit of integer i.

Then the selection and xor-ing of integers can be represented as A * x, where x is a vector of size n that has 1-s at positions of selected integers. This has to be over GF(2), so multiplication is the standard one and addition is XOR. So you are solving maximize(|x|) subject to Ax = 0.

Upvotes: 1

Related Questions