Dividing an array with equal XORs

Question

i don't know how to go about this problem >>

Given an array of integers, we need to divide that array into two parts such that

1) xor of 1st set is equal to that of second

2) difference between sum of elements of two parts is maximum.

for example:

if given array is [4,2,6]

then it can be divide into [2],[4,6],

          where xor(2) = 010
                xor(4,6) = 100^110 = 010 = xor(2)

and difference between sums of two parts = (4+6)-2 = 8(max difference possible which satisfies the above constraints).

(if it is not for the second constraint, dividing the array into parts with equal sum would have been sufficient).

Answer 1

This is a trick question.

If you have integers a1...an and you can divide them into two parts such that their XORs are equal, this just means that a1 xor a2 xor ... xor an equals zero. When that holds, ANY partition works, e.g. (a1) xor (a2 xor a3 xor ... xor an) == 0 by the above, so it must be that a1 == a2 xor ... xor an. Hence ANY partition works. Given that, you just either select an empty partition and full partition, if that is allowed, or the smallest integer into a singleton partition and put everything else into the second one.