Given a sorted array of distinct non-negative integers, find smallest missing element in it.

For example,

**Input: **A[] = [0, 1, 2, 6, 9, 11, 15]

**Output: **The smallest missing element is 3

**Input: **A[] = [1, 2, 3, 4, 6, 9, 11, 15]

**Output: **The smallest missing element is 0

**Input: **A[] = [0, 1, 2, 3, 4, 5, 6]

**Output: **The smallest missing element is 7

A simple analysis of the problem shows us that the smallest missing number would be the index of the element which is not equal to its element. For instance,

A[] = [0, 1, 2, 6, 9, 11, 15]

Here the smallest missing element is 3 as 6 is present at index 3 (instead of element 3). If all elements in the array are at their right position (say A[] = [0, 1, 2, 3, 4, 5] ), then the smallest missing number is equal to size of the array i.e. 6 in this case.

A simple solution would be to run a **linear search** on the array and return the first index which doesn’t match with its value. If no mismatch happens then return the size of the array. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is sorted.

We can easily solve this problem in O(log(n)) time by modifying binary search algorithm. The idea is to compare the mid index with the mid element. If both are same then the mismatch lies in the right sub-array else mismatch lies in the left sub-array. So we discard one half accordingly and recurse for the other.

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <stdio.h> // Function to find smallest missing element in a sorted // array of distinct non-negative integers int smallestMissing(int arr[], int low, int high) { // base condition if (low > high) return low; int mid = low + (high - low) / 2; // if mid index matches with the mid element, then the mismatch // lies on the right half if (arr[mid] == mid) return smallestMissing(arr, mid + 1, high); else // mismatch lies on the left half return smallestMissing(arr, low, mid - 1); } // main function int main(void) { int arr[] = { 0, 1, 2, 3, 4, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); int low = 0, high = n - 1; printf("The smallest missing element is %d", smallestMissing(arr, low, high)); return 0; } |

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class SmallestMissing { // Function to find smallest missing element in a sorted // array of distinct non-negative integers public static int smallestMissing(int[] A, int left, int right) { // base condition if (left > right) { return left; } int mid = left + (right - left) / 2; // if mid index matches with its value, then the mismatch // lies on the right half if (A[mid] == mid) { return smallestMissing(A, mid + 1, right); } else { // mismatch lies on the left half return smallestMissing(A, left, mid - 1); } } public static void main(String[] args) { int[] A = { 0, 1, 2, 3, 4, 5, 6 }; int left = 0, right = A.length - 1; System.out.println("The smallest missing element is " + smallestMissing(A, left, right)); } } |

`Output:`

The smallest missing element is 7

The time complexity of above solution is O(log(n)) and auxiliary space used by the program is O(log(n)) for call stack.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Isn’t the auxiliary space also O(log n) due to recursion stack?

Thanks. We have updated the complexity. Happy coding 🙂