Home » Algorithms

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.

Solution

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(n²) 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

#include<stdio.h>
#include<stdlib.h>

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

	for(int i=0;i<n-1;i++){
		//xoring all elements
		x^=a[i];               
	}
	for(int i=1;i<=n;i++){
		//xoring 1 to n
		y^=i;
	}

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

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

	printf("enter your range\n");
	scanf("%d",&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++){
		scanf("%d",&a[i]);
	}
	// function to check duplicate exists or not
	printf("\nthe missing number is %d\n",missingNo(a,n)); 
	
	return 0;
}

Output

enter your range
5
enter elements leaving one nummber in the range 1 to n
2
4
3
5

the missing number is 1

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

Space complexity: O(1)