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.