Home » Technical Interview Questions » Array Interview Questions » Find Smallest Missing Number in a Sorted Array

Find Smallest Missing Number in a Sorted Array


Reading Time - 1 mins

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

Approach 1 for Find Smallest Missing Number in a Sorted Array

Here we just simply comparing the index and the array element if the array element is greater than, that number(i) is missing. Now move to the implementation using c++ language.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
      if(a[i]>i)
      {
        cout<<i<<endl;
        return 0;
      }
  }
  cout<<n<<endl;
  return 0;
}
9 11
0 1 2 3 4 5 8 9 10
6

Complexity Analysis for Find Smallest Missing Number in a Sorted Array

Time Complexity – O(N) where n represents the size of the array. Here we traverse the array and once we find the answer then print it and return.

Space Complexity – O(1) because we don’t use any auxiliary space here.

Approach 2 for Find Smallest Missing Number in a Sorted Array

Here we use the concept of binary search because the array is already sorted. Here we search for each value of i in the range from 0 to M. If the element not found then print that element and return.

READ  Merging Intervals

Algorithm

  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.

Explanation

Input array:

    01245

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

C++ Program for Find Smallest Missing Number in a Sorted Array

#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 n,m;
  cin>>n>>m;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<m;i++)
  {
    if(!binary_search_missing(a,0,n,i))
    {
      cout<<i;
      return 0;
    }
  }
  cout<<m;
  return 0;
}
9 15
0 1 2 3 4 5 6 7 8
9

Complexity Analysis

Time Complexity – O(MlogN) where M is a range of elements and N is the size of the array. Here we search for every value of i in the range 0 to M then it leads us to O(mlogn) time complexity.

Space Complexity – O(1) because we don’t use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions