4
$\begingroup$

I have $N$ values, $a_1,a_2,a_3\ldots a_N$. Now let us say i could increase any of these values by any amount such that the XOR sum becomes zero.

$$(a_1+d_1) \oplus (a_2+d_2) \oplus \cdots \oplus (a_n+d_n) =0 $$

i need to find the deltas $d_1,d_2,d_3,\ldots,d_n$ such that the sum of deltas is minimized. any delta , $d_k \ge 0$.

$N$ could be up to $100$ in my case.

Could you please tell if there is any known way to compute it.

Many thanks

  • 0
    Sounds hard. Wouldn't surprise me if it was NP-complete.2012-06-28
  • 0
    Which of your signs are plus and which are XOR? If + is plus, you better allow dn to be less than zero or you will never get there.2012-06-28
  • 0
    (+) is xor sign2012-06-28
  • 0
    [Similar post on cs.SE](http://cs.stackexchange.com/q/2590/98).2012-07-04

1 Answers 1