#include <iostream>
#include <vector>
/*
The essence of O(1) complexity is that the algorithm performs a fixed number of operations,
no matter how large or small the input is. This characteristic ensures that the performance
remains consistent and does not degrade with increasing input size.
*/
int findMissingNumber(const std::vector<int>& vec) {
int size = vec.size();
// the formula for the sum of the first n natural numbers
long expected_sum = (long)(size + 1) * (size + 2) / 2;
long actual_sum = 0;//N(n + 1)/2
for (int num : vec) actual_sum += num;
return (int)(expected_sum - actual_sum);
}
int main() {
std::vector<int> vec = {1, 2, 4, 5, 6};
std::cout << "Missing number: " << findMissingNumber(vec) << std::endl;
}
/*
run:
Missing number: 3
*/
