I can see how the xor solution works for an array like [1,2,1,3,2,4,3,...], where at most 2 numbers are combined with xor before one gets cancelled. But Let's say the array is arranged as [1,2,3,4,5 1,2,3,4,5,6]. Then the cumulative xor of the first five elements should be able to keep [the information] for all these five numbers, so that they get cancelled, one by one, after the 6th element. How is that possible?
In fact, it does't keep all the information;
1^2^3 equals 0001^0010^0011=0011^0011=0
you may see these numbers in this way:
1 0001 2 0010 3 0011 4 0100 1 0001 2 0010 3 0011 4 0100 5 0101 0345----(trans odd to 1, even to 0)--→0101=5
now you can see, to every bit, pair numbers give it 2 signs and contribute a 0, the number which appear only once will be "left" in the end.
Xor is both associative and commutative, so you can reorder at will and still get the same result. The result of 1^2^3^4^5^1^2^3^4^5^6 is the same as 1^1^2^2^3^3^4^4^5^5^6.
You're certainly familiar with that from addition, where you're not surprised that 1+2+3+4+5+1+2+3+4+5+6 is the same as 1+1+2+2+3+3+4+4+5+5+6.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.