Microsoft

# `Microsoft` `Software Development Engineer` Interview Question *(student candidate)*

`"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."`

Part of a `Software Development Engineer` Interview Review - one of `3,408` `Microsoft` Interview Reviews

`Microsoft`

Answers & Comments

votes

/* 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;

}

votes

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.

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

votes

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();

}

vsonFeb 18, 2013