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

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

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  Count Pairs Whose Products Exist in Array

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
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup