Single number from Leetcode

The solution is trivial but the question poses the challenge : Could you implement it without using extra memory?

How though ? One pass through the array, it left us with no useful information. Then I click tags, bit manipulation is in there ? Hmm, How (again). Then I look through wikipedia and found that XOR could identify the odd number of bits… Does it apply here? Yes…

Example : 1^1^2^2^4 => 4 . XOR is either one but not both making the pair of 1 and 2 clearing each other out, so the condition that all number except on appear twice in the array is a clue. XOR is commutative so : 1^2^1^2^4 still brings us back to 1^1^2^2^4 therefore we have 4 as the result.

Yay

### Like this:

Like Loading...

*Related*