Lonely Integer - XOR Integer Pairs
From Hacker Rank, Lonely Integer Challange
Taking an array of integers, where it a guarenteed that the size is odd, and all enteries bar one is a pair, return the integer that only appears once.
I knew there must be a trick to this however I didn’t figure it out. I implemented a basic solution using a map to count instances which was obviously O(N) in time.
However since there are always pairs of numbers, it is much faster to do a bitwise XOR operation, as the pairs of numbers. As a small proof:
So the resulting code will be much quicker and easier