How can I find minimum number required to add to sequence such that their xor becomes zero

Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers.

Consider the following examples :

-
For $1, 3$ the answer is $2$; adding $2$ to $1$ we get $3 \oplus 3=0$.

-
For $10, 4, 5, 1$ the answer is $6$; adding $3$ to $10$ and $3$ to $5$ we get $13 \oplus 4 \oplus 8 \oplus 1 = 0$.

-
For $4, 4$ the answer is $0$, since $4 \oplus 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.

It seems to me that $a = a_i \oplus \dots \oplus a_n$ holds all necessary information: the $1$bits in $a$ are the bits you need to flip in (exactly) one of the $a_i$. As you are only allowed to add, you have to find one $a_i$ where the corresponding bit $j$ is $0$ and flip it -- this causes the same cost for all $a_i$, that is $2^j$, so the choice does not matter. Trouble begins if there is no such $a_i$.

That is why you have to do this iteratively and work from the least significant bit upwards. Proceed as above; if there is no suitable $a_i$, choose the $a_i$ with the maximum number of $1$ bits left of the current position -- this increases the chance of finding a suitable candidate in future iterations --, flip the bit and carry over, that is flip all ones to the left until you flip a zero to a one. Note that we still add $2^j$). As carry propagates only to the left, earlier choices are not invalidated. Recompute $a$ and continue with $j+1$; iterate until you have $a=0$.

Note that this is only a heuristic as far as I can tell: the choice of $i$ may be suboptimal if it causes many bits in $a$ to become non-zero. I am not sure if this can be avoided.

StackExchange Computer Science Q#2590, answer score: 5