Interview Question

Software Development Engineer Interview(Student Candidate) Redmond, WA

You have an array of length n consisting of the integers

  from 0 through n-1 exactly once each, except for one which is missing. Find the missing number. The numbers can be in any order.
Answer

Interview Answer

3 Answers

0

This problem can be solved in two ways:

// 1st approach
- if the array can be modified, sort it
- go through the sorted array until you find an element which does not equal its index
- O(n logn) time + 0 space

int findMissing1(vector<int>& arr)
{
    // sort the array
    std::sort(arr.begin(), arr.end());

    // all elements should equal to their index, except for the missing one
    for (int i = 0; i < arr.size(); ++i)
        if (i != arr[i])
            return i;

    // should not happen
    return -1;
}

// 2nd approach
- else, create a set (or vector, etc.) which contains elems 0 through N (inclusive)
- iterate through the stack, erasing all of the arrays elements
- in the end, the stack will contain one element -- the missing one
- O(n) time + O(1) space

int findMissing2(const vector<int>& arr)
{
    // create a set to hold ALL elements from 0 to N
    std::set<int> numSet;
    for (int i = 0; i < arr.size() + 1; ++i) // note +1
        numSet.insert(i);

    // now delete all arr's elements from the set
    for (int i = 0; i < arr.size(); ++i)
        numSet.erase(numSet.find(arr[i]));

    // the remaining element is the missing one
    return *numSet.begin();
}

vs on Feb 18, 2013
7

/* getMissingNo takes array and size of array as arguments*/
int getMissingNo (int a[], int n)
{
    int i, total;
    total = (n+1)*(n+2)/2;
    for ( i = 0; i< n; i++)
       total -= a[i];
    return total;
}

Anonymous on Feb 18, 2013
0

I believe it should be total = (n-1)*(n)/2. The sum of the series 1 - n is (n*(n+1))/2. Subtract 1 since we are starting from zero and we get ((n-1)*(n))/2.

Anonymous on Sep 18, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up