Find Missing Number with Vector

c plus plusThis 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;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s