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