Problem¶

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Constraints:

• n == nums.length
• 1 <= n <= 10**4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Example 1:

**Input:** nums = [3,0,1]
**Output:** 2
**Explanation:** n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Solve¶

Bit manipulation¶

We can use xor to get needed information:

• Xor two same number will return 0
• While Xor any number with 0 return it self

We already know nums array is range [0..len(nums)] with a missing number. By xor all available number in range [0..len(nums)] again, we effectively negative all exist number in nums array, leaving only one missing number left being xor with 0.

Which mean, the sum s of xor all number is our needed result missing number

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        s = 0
        for i, x in enumerate(nums):
            s = s ^ i ^ x

        s = s ^ len(nums)
        return s

Same implement in C

int missingNumber(int* nums, int numsSize){
    int s = 0;
    for (int i = 0; i < numsSize; i++) {
        s ^= i ^ nums[i];
    }

    s ^= numsSize;
    return s;
}

Sort, Counting, Caching, Binary search tree…¶

Try to find missing number by checking all possible answer one by one:

• Loop through nums array, remember all found number
• Checking again in range [0..len(number)] and our chosen caching information from previous step to quickly separate: which number is in nums array, and which is the missing one

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        isFound = [False] * (len(nums)+1)
        for x in nums:
            isFound[x] = True
        for i, f in enumerate(isFound):
            if not f:
                return i
        return len(nums)