|
There is an array of size 50 that is expected to contain all the numbers. ....
Microsoft Interview Questions and Answers
(Continued from previous question...)
100. There is an array of size 50 that is expected to contain all the numbers. ....
Question:
There is an array of size 50 that is expected to contain all the numbers from 1 to 50 (every number occuring only once). But there is one number in the array that doesnot satisfy this condition i.e. one number is either duplicate or outside 1 to 50 range. Find the correct number that is missing in the array.. O(n) soln required.
maybe an answer:
1. Iterate thru the array to find
SUM = sum of all elements.
SQUARESUM = sum of square of elements.
2. IdealSUM = n*(n+1)/2
3. IdealSQUARESUM = n*(n+1)*(2n+1)/6
4. Let 'a' is the missing number and 'b' is the number that is in place of 'a'.
5. IdealSUM - SUM = a-b
6. IdealSQUARESUM - SQUARESUM = a^2 - b^2 = (a+b)(a-b)
7. from step 5 and 6 we can get the value of (a+b)
8. from step 7 and step 5 we can get values of 'a' and 'b'
maybe an answer2:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int FindBadNumber(vector<int> &v) {
for (int i = 0; i < v.size(); ++i) {
while (v[i] != i + 1) {
if (v[i] > v.size() || v[i] < 1)
return v[i];
if (v[i] == v[v[i] - 1])
return v[i];
swap(v[i], v[v[i] - 1]);
}
}
return -1;
}
int main() {
vector<int> v;
for (int i = 1; i <= 50; ++i) {
v.push_back(i);
}
v[0] = -1;
random_shuffle(v.begin(), v.end());
cout << "Bad number is: " << FindBadNumber(v) << endl;
}
(Continued on next question...)
Other Interview Questions
| 