Table of Contents
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.
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
- Run a loop from 0 to M-1 and do
- Binary search for each element in the range and see if the number exists or not.
- [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.
- 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.
Space Complexity – O(1) because we don’t use any auxiliary space here.