Find a missing number in an array

Problem

Find the missing number from the list of 99 distinct numbers which are in [0, 99]

Solution

/*

============================================================================

Author : James Chen

Email : a.james.chen@gmail.com

Description : Find the missing number from the list of 99 distinct numbers which are in [0, 99]

Created Date : 17-06-2013

Last Modified : 21-06-2013

============================================================================

*/

#include <iostream>

#include <vector>

#include <iomanip>

#include <algorithm>

#include <functional>

#include <iterator>

#include <numeric>

using namespace std;

int main(int argc, char* argv[])

{

srand(4);

vector<int> vec(100);

vec[1] = 2;

int i = 0;

generate_n(vec.begin(), 100, [=]() mutable -> int { return i++; });

int expectedSum = accumulate(vec.begin(), vec.end(), 0);

cout << "Expected sum is " << expectedSum << endl;

int missingNum = rand() % 100;

cout << "The missing number will be " << missingNum << endl;

remove(vec.begin(), vec.end(), missingNum);

vec.resize(vec.size() - 1);

random_shuffle(vec.begin(), vec.end());

int actualSum = accumulate(vec.begin(), vec.end(), 0);

cout << "Actual sum is " << actualSum << endl;

missingNum = expectedSum - actualSum;

cout << "Find missing num: " << missingNum << endl;

return 0;

}

Output

Expected sum is 4950

The missing number will be 51

Actual sum is 4899

Find missing num: 51

Press any key to continue . . ..