Find Smallest Missing Number in a Sorted Array  


Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Capital One Cisco eBay Facebook Goldman Sachs Google IBM JP Morgan Microsoft Nvidia Oracle PayPal ServiceNow Yandex
Arista Networks Array Math

Problem Statement  

In the “Find Smallest Missing Number in a Sorted Array” problem we have given an integer 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

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.

Implementation

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;
}

Java Program

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]>i)
            {
              System.out.println(i);
              temp=1;
              i=n;
            }
        }
        if(temp==0)
        System.out.println(n);
    }
}
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 it.

See also
Check in binary array the number represented by a subarray is odd or even

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.

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:

    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

Implementation

C++ Program

#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;
}

Java Program

import java.util.Scanner;
class sum
{
    public static int binary_search_missing(int arr[],int low,int high,int x)
    {
      if(low > high)
      return 0;
      int mid = low + (high - low)/2;
      if(arr[mid]==x)
        return 1;
      else if(arr[mid] > x) 
        return binary_search_missing(arr,low,mid-1,x);
      else
        return binary_search_missing(arr,mid+1,high,x);
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int temp=0;
        for(int i=0;i<m;i++)
        {
          if(binary_search_missing(arr,0,n,i)==0)
          {
            System.out.println(i);
            temp=1;
            i=n;
          }
        }
        System.out.println(m);
    }
}
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.

See also
Partition Equal Subset Sum

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

References