missing number Algorithm

The Missing Number Algorithm is an efficient technique used in computer programming and mathematics to identify a missing number within a given sequence of numbers. This algorithm is particularly useful when dealing with large data sets or continuous numerical sequences, where it might be challenging to spot the missing number manually. The primary concept behind this algorithm is to leverage the properties of arithmetic progressions or utilize the properties of bitwise operators to find the missing number quickly. In the most common approach, the algorithm calculates the sum of all the numbers in the given sequence and subtracts it from the expected sum of the continuous sequence. The difference between these two sums gives the missing number. Another approach involves using the XOR operation on the index and the corresponding values in the given sequence. The cumulative XOR of both the indices and the values will result in the missing number. This method is particularly efficient as it has a linear time complexity and does not require any additional memory. Overall, the Missing Number Algorithm is an essential tool in various problem-solving situations, from coding interviews to real-world applications.
/**
 * 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;
}

LANGUAGE:

DARK MODE: