Algorithm ：Missing Number

Q: Missing Number

description: 

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

A:  Bit Manipulation

Intuition

We can harness the fact that XOR is its own inverse to find the missing element in linear time.

Algorithm

Because we know that nums contains $n$ numbers and that it is missing exactly one number on the range $[0..n-1]$, we know that $n$ definitely replaces the missing number in nums. Therefore, if we initialize an integer to $n$ and XOR it with every index and value, we will be left with the missing number. Consider the following example (the values have been sorted for intuitive convenience, but need not be):

Index	0	1	2	3
Value	0	1	3	4

Python3
class Solution:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing

Complexity Analysis

• • Time complexity : O(n)

Assuming that XOR is a constant-time operation, this algorithm does constant work on nn iterations, so the runtime is overall linear.

• • Space complexity : O(1)

 

This algorithm allocates only constant additional space.