Missing Number

Given an array containingndistinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.

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

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

Brainstorm

I first considered this problem from a more ideal circumstance: what if the array was already sorted? Then we could simply use binary search to find out the missing number (by looking at which half is uneven). Of course, again, this relies on the assumption that the array is sorted, but we will address this problem in a more general solution later.

Approach #1: Binary Search

The conditions for moving the indices are:

• If an element at mid is greater than the index mid, this means somewhere before or on the element, a number was skipped, and we move the indices to the left half of the current array.
• Otherwise, we know at least the elements before mid are complete, and we shift to the right half of the current array.

int missingNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int start = 0, end = nums.size();
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] > mid)
            end = mid;
        else
            start = mid + 1;
    }
    return start;
}

Time complexity: $$O(n log n)$$

Binary search is indeed logarithmic time, but it ends up being dominated by the time complexity of sorting, which is basically the overall time complexity of O(n log n).

Space complexity: $$O(1)$$