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