Missing number#

Levels: level-2

Data structures: bits, array

Practice Link#

LeetCode

Description#

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

Note:

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

Examples#

1Input: [3,0,1]
2Output: 2

1Input: [9,6,4,2,3,5,7,0,1]
2Output: 8

Thinking#

We can harness the fact that XOR is its own inverse to find the missing element in linear time.
Because we know that nums contains n numbers and that it is missing exactly one number on the range [0..n-1][0..n−1], we know that nn definitely replaces the missing number in nums.
Therefore, if we initialize an integer to nn and XOR it with every index and value, we will be left with the missing number.

Python Solution#

1class Solution:
2    def missingNumber(self, nums):
3        missing = len(nums)
4        for i, num in enumerate(nums):
5            missing ^= i ^ num
6        return missing