This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company? Learn More.

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

Answers & Comments

▲

7

▼

of 7votes

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

}

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;

}

▲

0

▼

of 0votes

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

Tags are like keywords that help categorize interview questions that have something in common.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

We're sorry but your feedback didn't make it to the team. Your input is valuable to us – would you mind trying again?

Browse:

Copyright © 2008–2014, Glassdoor. All Rights Reserved. Your use of this service is subject to our Terms of Use and Privacy & Cookies Policy. Safe Harbor Notice. Glassdoor ® is a registered trademark of Glassdoor, Inc.

Sign In with Google

Sign In with Facebook

Everything you view and do on Glassdoor is private

Or

votes

// 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, 2013Flag Response