Finding the missing number

In this article, we are going to see an advance algorithm to find a missing number in an array of length n range from 1 to n.
Submitted by Radib Kar, on October 30, 2018

Problem statement

We are given a list of n-1 integers and the integers range from 1 to n. There are no duplicates in the list. Only one of the integer from 1 to n is missing. We need to find the missing number in O(n) time complexity.


The simplest solution is to take each number from 1 to n and to check whether it exists in the array or not. But such approach has O(n2) time complexity. Thus we need to find some advance algorithm to reduce the time complexity.

The algorithm is illustrated below:

  1. XOR all the elements presented in the array. Let the result be x.
  2. XOR all numbers from 1 to n. Let the result be y.
  3. XORing x & y gives the missing number.

C code for implementation


int missingNo(int* a, int n){
	int x=0,y=0;

	for(int i=0;i<n-1;i++){
		//xoring all elements
	for(int i=1;i<=n;i++){
		//xoring 1 to n

	//xoring x & y outputs missing number
	return x^y;                 

int main()
	int n,x,count=0;

	printf("enter your range\n");

	printf("enter elements leaving one nummber in the range 1 to n\n");

	// dynamic array created for n-1 elements
	int* a=(int*)(malloc(sizeof(int)*(n-1))); 
	for(int i=0;i<n-1;i++){
	// function to check duplicate exists or not
	printf("\nthe missing number is %d\n",missingNo(a,n)); 
	return 0;


enter your range
enter elements leaving one nummber in the range 1 to n

the missing number is 1

Time complexity: O(n) (for scanning the array)

Space complexity: O(1)

Related Tutorials


Comments and Discussions!

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© some rights reserved.