Missing Number

Problem statement:

You are given an array of numbers from 1 to n, in any order, one number will be missing. You need to find a missing number.

Example:

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

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

Solution in C++

#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;

}

Output:

Missing number using math = 6
Missing number using xor = 6

List Of Tutorials available in this website: