The overused bitter

Given an array with all elements but one occurring twice, find the one that does not repeat.

Yoops!

Howdie.

Chances are that you mumble the answer to this question in your dreams, given how common this question is, and how easy its solution is.

And interviewers know this. So, too make things tough, which is what they’re paid to do, they try to delve into the logic behind how you came up with this solution, and that’s where a number of us goof up.

Or we used to, so far.

Not anymore.

A brute force solution will definitely be to maintain a map of each element in the array, with its count. And finally, return the element with count = 1.

This solution needs extra space, aka, an extra data structure, a map, that maps each element to the number of times it occurs.

That’s O(N) extra space.

Can we make it better?

Yep. Bit logic is the answer.

Know of a concept called XOR? A XOR between 1 and 1, or 0 and 0 gives 0, a XOR of 0 and 1, or 1 and 0 gives 1.

In computers, a XOR is denoted by ‘^‘.

Now, consider a number, say 13. What will be 13^13?

0.

How?

13 in binary representation is 1101.

When we XOR a multi digit number, we XOR all digits individually. Thus

1101 ^ 1101 = 0000.

Got it? The XOR of any number with itself will be 0!!

Now try and think for 10 seconds before going ahead. How can we use this in our question?

Yep. If we XOR all elements of the array, the elements repeating will all XOR zero with each other. The one element that’s present only once will remain.

And that’s it. That’s the solution.

XOR all elements of the array. The final answer is the element that’s present only once.

Time Complexity : O(N)

Space Complexity : O(1), since we aren’t using any extra data structure.

Now try working out what can we do when all elements of the array, but one, occur thrice.

That’s the topic for the next post.

Cheers