Given a sequence of natural numbers, you can add any natural number to any numbe

Question

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?3=0.

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

For 4,4 the answer is 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.

Explanation / Answer

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

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 ai, choose the ai 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 2j). 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.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.