Find the missing number from Array of 1 to N numbers

One number is missing from an array of numbers from 1 to N. Find the missing number.

Method 1

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

We use Simple Mathematics formula as shown in below algorithm

Algorithm

1. We know the sum of numbers from 1 to N is given by the formula

      N*(N+1)/2.

Let us call this as real_sum.

2. And then we sum the elements present in the array and let us call it missing_sum.

3. Simple the difference between real_sum and missing_sum is the missing number as it was not added while computing the missing_sum.

Program for Method 1:

Try It
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
	int arr[] = {1,2,3,4,6,7,8,9};
	int N = 9;
	
	ll Sum =N*(N+1);
	Sum = Sum>>1;  //if all numbers are present then the sum is N*(N+1)/2
	ll sum = 0;
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
	 	sum += arr[i]; //sum of elements actually present in the array
	 	
	cout <<"Missing number is "<<Sum-sum <<endl;
	
	return 0;
}




Method 2

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

We use the concept of XOR operation.

As we know,

A xor A = 0   ------------- Property 1

i.e. xor of 2 similar elements is zero.

Also,

A xor 0 = A   ------------- Property 2

i.e. xor of any element with zero gives the same number.

Algorithm

1. We compute the XOR of all the values from 1 to N and say it is X.

2. We compute the XOR of all the values in the array and say it is Y.

3. Now when we do (X xor Y) we basically are XORing all values twice except the missing number which came only once. Thus the final value is nothing but the missing number by property 2 of XOR.

Input: 1 2 3 4 6 7 8 9

output: 5

Program for Method 2:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
	int arr[] = {1,2,3,4,6,7,8,9};
	int N = 9;
	
	int X = 0,Y = 0;
	
	for(int i=1;i<=N;i++)
		X ^= i;	//XOR of all elements from 1 to N
	
	for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
		Y ^= arr[i]; //XOR of all elements in the array
		
	int missing_Num = X^Y;
	cout <<"Missing number is "<<missing_Num<<endl;
	
	return 0;
}
Try It


Next > < Prev
Scroll to Top