xor of sequence of numbers

c
c-plus-plus
xor

#1

You are given with a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. Your goal is to minimize the sum of added numbers.

e.g. Consider the following examples :

sequence : 1, 3 answer : 2, adding 2 to 1 we get 3^3=0.

sequence : 10, 4, 5, 1 answer: 6, adding 3 to 10 & 3 to 8 we get 13^4^8^1 = 0.

sequence : 4, 4 answer : 0, since 4^4 = 0.

I tried working on binary representations of sequence number but it got so complex. I want to know if there is any simple and efficient way to solve this problem.


#2

Please add link, it seems to be interesting problem :wink: My idea is that you do xor for all elements in sequence and then you simply want to eliminate most significant bit in result as first…


#3

@betlista: If you do xor of all elements you will only get an upper bound of value to be added.