Solution Review: Missing 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 math below 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, res = 0.
• Iterate over array elements from 0 to length + 1 and do ^ of each with the above-initialized variable.
• Iterate over all the elements and store the value in the variable.