Missing number in an array

You are given an array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 . You need to find the missing number.

We know that sum of of numbers from 0 – n-1  is n*(n-1)/2.

Now, we scan all numbers in the array, we could get the sum of all numbers. Only missing number in the array is difference of both the sums.

This solution can be implemented with the following code:

int getMissingNumber(int* arr, int n)
{
	if(n <= 0)
		return -1;
	int sum1 = 0;
	
	for(int i = 0; i < n; ++i)
		sum1 += arr[i];
		
	int sum2 = n * (n + 1) / 2;

	return sum2 - sum1;
}

Since we have to scan all numbers in the array, it has complexity O(n) time if the size of array is n.

Now if you are given a sorted array of n – 1 unique numbers in the range from 0 to n – 1. There is only one number missing in the range from 0 to n – 1 . You need to find the missing number.

Of course, we could use the solution above to solve this problem, which costs O(n) time. This solution does not utilize the properties of sorted arrays.

Since numbers from 0 to n – 1 are sorted in an array, the first numbers should be same as their indexes. That’s to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(log n) time based on the binary search algorithm as implemented below:

int getMissingNumberSorted(int* arr, int n)
{
    if( n <= 0)
        return -1;

    int left = 0;
    int right = n - 1;
    while(left <= right)
    {
        int middle = (right + left) / 2;
        if(arr[middle] != middle)
        {
            if(middle == 0 || arr[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }

    return -1;
}