Search⌘ K
AI Features
Home
Courses
Grokking Bit Manipulation for Coding Interviews

Solution Review: Missing Number

Discover how to use bitwise XOR to efficiently find the missing number in an array. This lesson guides you through the XOR properties, algorithm implementation, and complexity analysis, helping you master a key bit manipulation technique crucial for coding interviews.

We'll cover the following...

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
...