Solution Review: Single Number

Solution review: Bit manipulation

We are dealing with bit manipulation and want to solve all of these problems with Bitwise operators.

Concepts

If we take XOR of zero and a bit, it will return that bit.

a ^ 0 = a

If we take XOR of two same bits, it will return 0.

a ^ a = 0

For n numbers, the below math can be applied.

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;

For example:

1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;

So, we can XOR all bits together to find the unique number.

Algorithm

• Initialize a variable to 0.
• Iterate over all the elements and store the value in the variable.