Monday, February 4, 2013

No. 37 - Missing Number in an Array

Problem 1: An array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.

Analysis: If we scan all numbers in the array, we could get the sum of all numbers. The sum is denoted as sum1.

Additionally, we could also get the sum of all numbers in the range from 0 to n - 1, which is n*(n-1)/2. The sum is denoted as sum2.

The only number missing in the array is the difference between sum2 and sum1.

This solution can be implemented with the following code:

int getOnceNumber_unsorted(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        return -1;

    int sum1 = 0;
    for(int i = 0; i < length; ++i)
        sum1 += numbers[i];

    int sum2 = length * (length + 1) / 2;
    return sum2 - sum1;
}

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

Problem 2: An sorted array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.

Analysis: Of couse, 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. If the missing number is denoted as m. Numbers less then m are located at cells with indexes same as values.

The number m + 1 is located at a cell with index m, The number m + 2 is located at a cell with index m + 1, and so on. We can see that, the missing number m is the first cell whose value is not identical to its value.

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(lgn) time based on the binary search algorithm as implemented below:

int getOnceNumber_sorted(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        return -1;

    int left = 0;
    int right = length - 1;
    while(left <= right)
    {
        int middle = (right + left) >> 1;
        if(numbers[middle] != middle)
        {
            if(middle == 0 || numbers[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }
  
    if(left == length ) // corrected by Kyunghee Kim
        return length;

    return -1;
}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to
http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

11 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This works if the items in the array starts from 0 to n ,what if the items starts from n to m in the array then here is a solution:

    Assumption : array sorted ascending
    int findMissingNumber(int [] a)
    {
    int startIndex=0;
    int endIndex =a.length-1;
    int midIndex =(startIndex+endIndex)>>1;

    while( startIndex < endIndex ){

    if( a[midIndex] -a[startIndex] !=midIndex-startIndex)
    {
    if( midIndex -startIndex ==1 && a[midIndex] -a[startIndex] >1)
    {
    return midIndex-1;
    }
    endIndex =midIndex;
    midIndex= (startIndex+endIndex)>>1
    }
    else if( a[endIndex] -a[midIndex] !=endIndex-midIndex){

    if( endIndex -midIndex ==1 && a[endIndex] -a[midIndex] >1)
    {
    return midIndex+1;
    }
    startIndex =midIndex;
    midIndex= (startIndex+endIndex)>>1
    }
    // Not found
    return -1;
    }


    }

    ReplyDelete
  3. Hi, how about this problem?
    1~n unique numbers, but been written as string and all numbers are head-tail linked, in random order, find out the missing number.
    For example, input: 1 to 13, 12 numbers, been written as "2113871101269"
    The sum will not work. buy I think it could be solved by dynamic programming?

    ReplyDelete
    Replies
    1. u can solve it from the last by using %10 in every loop and check in every loop whether the next digit is 1 if 1 take it as 2 digit or as one digit only for 3 times bcoz of(0 to 13 )values

      Delete
    2. and also check whether the ones number is 1 to 3

      Delete
  4. Hi Harry, in the solution for the problem 1, should the sum2 be length*(length-1)/2, i.e., n*(n-1)/2? Because the smallest number in the array is 0 not 1.

    ReplyDelete
    Replies
    1. The code is correct, because the length of the array is n-1, rather than n. One number in the range from 0 to n-1 is missing.

      Delete
  5. Great thanks to Kyunghee Kim, who helped to correct an issue when the missing number is the greatest number in the sorted array. The post has been updated with the fix.

    ReplyDelete
    Replies
    1. It should be

      if(left == length-1 )
      return (length-1);

      Delete
  6. int getOnceNumber_unsortedXOR(int* numbers, int length)
    {
    if(numbers == NULL || length <= 0)
    return -1;

    int i = 0, result = 0;
    do result ^= numbers[i]^i++;
    while( i < length );

    return result^i;
    }

    ReplyDelete
  7. class Solution {
    public:
    int missingNumber(vector& nums) {
    int r = 0;
    for (int i = 0; i<nums.size(); i++){
    r ^= i ^ nums[i];
    }
    return r ^ nums.size();
    }
    };
    URL: http://traceformula.blogspot.com/2015/09/missing-number-leetcode.html

    ReplyDelete