This one is simple, given an array containing all numbers from 1 to N with the exception of one print the missing number to the standard output. My solution makes use of vector. Expected complexity is O(N). As a side note, it has been said that this problem has been asked on Microsoft interviews.

#include <iostream> #include <vector> using namespace std; void find_missing_number(const vector<int> &v) { int total, i; total = (v.size()+1)*(v.size()+2)/2; for (i = 0; i < v.size(); i++) total -= v[i]; cout << total; }

Advertisements