Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without extra memory?
My initial conclusion was that no, you couldn’t. Since there’s not a range for the possible numbers in the array and the array isn’t already sorted, you can solve in linear time if you used an object to store counts, but you need that extra storage or sorting is O(n log n).
But see, I forgot about XOR (^). For those of you who don’t play with bits, exclusive or takes two binary numbers and for pair where one number has the bit flipped and the other doesn’t, the resulting number has the bit flipped.
So if you have a number and XOR it by 0, you get the number. If you have a number and XOR it by itself, you get 0.
Now, that’s helpful, but why would you care about XOR for this problem?
Let’s run through an example:
Because all of the values that appear twice will eventually cancel themselves out, you’re left with that one solitary element that has no partner. No extra storage necessary. Linear time.
Problem taken from LeetCode