forked from anmol098/algorithms_and_data_structures
-
Notifications
You must be signed in to change notification settings - Fork 0
/
missing_number.cpp
39 lines (35 loc) · 834 Bytes
/
missing_number.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
*
* For example,
* Given nums = [0, 1, 3] return 2.
*/
#include <iostream>
#include <vector>
int missingNumber( std::vector<int>& nums ) {
int missing_sum = 0;
for ( auto n : nums ) {
missing_sum += n;
}
int n = nums.size();
int expected_sum = 0;
if ( n % 2 == 0 ) {
expected_sum = (n/2) * (n + 1);
} else {
expected_sum = n * ( (n+1)/2 );
}
return expected_sum - missing_sum;
}
void printVec( std::vector<int> & vec ) {
std::cout << "Vec:";
for ( auto v : vec ) {
std::cout << v << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> vec{ 0, 1, 3 };
printVec(vec);
std::cout << "Missing number in above vector is :" << missingNumber(vec) << std::endl;
return 0;
}