Missing Number

Input: [0, 1, 3]
Output: 2

We can solve this problem by 2 methods:

1. Finding the sum of all the numbers

2. Using xor

Method 1: By finding the sum of all the numbers of the array

We know that the sum of all the first n natural numbers can be got by n*(n-1)/2.

So first we calculate the sum of “n” numbers.

Then we take the sum of all the numbers present in input array.

Then we subtract both of the result, we get our missing number,

Method 2: By using XOR

Step 1: We do XOR of all the elements of the array

Step 2: XOR for all the numbers from 1 to n

Step 3: We do XOR of above 2 results, we get our result

#include<iostream>
#include<vector>
using namespace std;

int missing_number_using_math(vector<int>& nums) 
{ 
    int len = nums.size();

    int sum = len * (len+1)/2;
    for(int i=0; i<len; i++)
        sum-=nums[i];
    return sum;
}

int missing_number_using_xor(vector<int>& nums) 
{ 
        int missing =0;
        for(int i=0; i<nums.size();++i) 
            missing ^= ((i+1)^nums[i]);
        return missing;
}


int main()
{
	std::vector<int> v = {0, 1, 2, 3, 4, 5, 7};

	cout<<"Missing number using math = "<< missing_number_using_math(v)<<endl;
	cout<<"Missing number using xor = "<< missing_number_using_xor(v)<<endl;

}