XOR applications

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.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s