Solution Review: Missing Number

We solved the problem using lookup (hashtable) and using the mathematical formula for the sum of n natural numbers, Let's solve this more efficiently using bit-level operations with XOR.

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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.