Solution
Compute sum of the list.
Compute desirable sum without missing number.
The missing number is desirable sum minus actual sum.
Question
Find the missing number from the list of 99 distinct numbers which are from 1-100
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
void InitList(vector<int>& vec)
{
int expectedMissingNum = rand() % 100;
cout << "The number " << expectedMissingNum << " is going to missing!" << endl;
for(int i = 1; i < expectedMissingNum; ++i){
vec.push_back(i);
}
for(int i = expectedMissingNum + 1; i <= 100; ++i){
vec.push_back(i);
}
}
int FindMissingNumber(vector<int>& vec)
{
int sum = accumulate(vec.begin(), vec.end(), 0);
return (1 + 100) * 100 / 2 - sum;
}
int main(int argc, char* argv[])
{
srand(0);
for(int i = 0; i < 10; ++i){
vector<int> vec;
InitList(vec);
cout << "Find the missing number: " << FindMissingNumber(vec) << endl << endl;
}
return 0;
}
Output
The number 38 is going to missing!
Find the missing number: 38
The number 19 is going to missing!
Find the missing number: 19
The number 38 is going to missing!
Find the missing number: 38
The number 37 is going to missing!
Find the missing number: 37
The number 55 is going to missing!
Find the missing number: 55
The number 97 is going to missing!
Find the missing number: 97
The number 65 is going to missing!
Find the missing number: 65
The number 85 is going to missing!
Find the missing number: 85
The number 50 is going to missing!
Find the missing number: 50
The number 12 is going to missing!
Find the missing number: 12
Press any key to continue . . .