Find smallest missing number in a sorted array

Find the smallest missing number in N sized sorted array having unique elements in the range of 0 to M-1, where M>N

Example:

Input: [0,1,2,3,4,6,7,8,9] → output: 5

Input: [0,1,2,4,5,6,7,8] → output: 3

Input: [0,1,2,3,4,5,6,8,9] → output: 7

Input: [0,1,2,3,4,5,7,8,9] → output: 6

ALGORITHM 1

TIME COMPLEXITY – O(N)

SPACE COMPLEXITY – O(1)

Linear Search, simply comparing the index and the array element if it is greater than, that number is missing.

Example:

Apply algorithm on Input array,

Program for Algorithm 1

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

int main()
{
	int M = 11;
	int arr[] = {0,1,2,3,4,5,8,9,10};
	int N = sizeof(arr)/sizeof(arr[0]);
	
		
	for(int i=0;i<N;i++)
	{
		if(arr[i] > i) //if array element is greater than i then that element is missing number.
			{
				cout<<"Missing element is "<<i<<endl;
				return 0;
			}
	}
	
	cout<<"Element "<<N<<" is missing\n";
	return 0;
}
Try It

ALGORITHM 2

TIME COMPLEXITY – O(MlogN), M is range of elements and N is size of array

SPACE COMPLEXITY – O(1)

 

  1. Run a loop from 0 to M-1 and do
  2. Binary search for each element in the range and see if the number exists or not.
  3. [0,1,2,4,5,6,7,8] is the given array so, here range is 0 to 8. Binary  search for every number from 0 to 8 in the array.
  4. Print the element which is missing first, it will be the smallest missing element.
Example:

Input array:

0

1

2

4

5

Apply algorithm on Input array,

M = 5,

For i = 0,

            Binary Search(0,input array) = True

For i = 1,

            Binary Search(1,input array) = True

For i = 2,

            Binary Search(2,input array) = True

For i = 3,

            Binary Search(3,input array) = False

Therefore, smallest missing element is = 3

Program for Algorithm 2

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

// code for searching element is present in array or not
//using binary search
bool binary_search_missing(int arr[],int low,int high,int x)
{
	
	if(low > high)
	return false;
	
	int mid = low + (high - low)/2;
	if(arr[mid]==x)
		return true;
		
	else if(arr[mid] > x) 
		return binary_search_missing(arr,low,mid-1,x);
	else
		return binary_search_missing(arr,mid+1,high,x);
		
}

int main()
{
	
	int M = 11;
	int arr[] = {0,1,2,3,4,5,8,9,10};
	int N = sizeof(arr)/sizeof(arr[0]);
	for(int i=0;i<M;i++)
	{
		if(!binary_search_missing(arr,0,N,i))// if binary_search return false we print the element
		{
			cout<<"Element "<<i<<" is missing\n";
			return 0;
		}
	}
	
	cout<<"Element "<<M<<" is missing\n";
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top