8
$\begingroup$

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 :

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

  2. 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$.

  3. 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.

$\endgroup$

migrated from stackoverflow.com Jul 2 '12 at 18:45

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ A clearer statement of the same problem from a different poster on math.SE can be found here, together with another answer. $\endgroup$ – Dilip Sarwate Jul 2 '12 at 20:47
  • $\begingroup$ Interesting problem. It looks like a subset sum problem where the sum operator is replaced with XOR and such that (if the subset doesn't XOR to 0) the set $(s_1,s_2,\ldots,s_n)$ is itself XORed with another set $\{0,1\}^n \cdot (k,k,\ldots,k)$... $\endgroup$ – user13675 Jun 9 '14 at 0:40
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

I don't actually have a solution, but here are a few ideas that came up.

If you look at the results of XORing all of the numbers in the sequence, that gives an upper bound on the number of additions you need to do. For example, in your example of $10, 4, 5, 1$, we have $10 \oplus 4 \oplus 5 \oplus 1 = 10$, so you know you don't have to add more than $8$ (because the 8-bit is the highest one set). Distributing up to eight "ones" distributed four ways, is a fairly small set of combinations. I can't remember that formula this late at night, but there's an $n!$ in there somewhere.

To give that statement a little bit more grounding, consider arbitrary integers $A,B$ such that $A \oplus B = 8$. The bits higher than bit 3 obviously all cancel out, so you can ignore them. For the lower four bits, they XOR to 8, so the worst possible case (in terms of number of ones you need to add ) is if $A=8$ and $B=0$ (all zeroes except for the highest bit) because you'll need to add +8 to B to get that top bit set. If there are any one bits set in either of the numbers, you need to add less.

Maybe you can start from this, and develop a tighter maximum amount to add.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.