Arrays: Find the missing number in a sorted array


Program to find the missing number from a sorted array that contains elements from 1 to n where
n is the total no of elements in the array

Eg: 3 is missing from the array [1,2,4] where n = 4

 
Approach

As the array is sorted, we can use a counter = 1 and compare this counter value with array cell value.
If the array cell value is different from counter, we know the missing number is counter and return it.
If the loop ends, we know the missing number is the last number in the array, so again we return the counter.

 
Complexity

Time Complexity: O(N)
Space Complexity: O(1)

The Time Complexity is O(N) as we are just looping through the array and finding the missing number
The Space Complexity is O(1) as no extra space is used in the algorithm

 
Java Code
class MissingNoFromSortedArray{
    
        // A function to find the missing number in a array with 1 to array.size + 1
        public static int getMissingNumber(int[] array) {
            // The counter starts from 1
            int counter = 1;
    
    
            for (int i = 0; i < array.length; i++) {
               // If the element is not equal to the counter then we can say counter is missing
               if (array[i] != counter) {
                   return counter;
               }
    
    
               // Increment the count by one
               counter++;
            }
    
    
            // If we reach the end of the array and no number is missing,
            // then the last element is missing from the array
            return counter;
        }
    
    
       public static void main(String[] args) {
           // In the below array, the number 7 is missing from the array
           int[] array1 = { 1, 2, 3, 4, 5, 6, 8, 9, 10 };
           System.out.println("The Missing number in array1 is: " + getMissingNumber(array1));
    
    
           // In the below array, the number 10 is missing from the array
           int[] array2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
           System.out.println("The Missing number in array2 is: " + getMissingNumber(array2));
    
    
           // In the below array, the number 1 is missing from the array
           int[] array3 = {2, 3, 4, 5, 6, 7, 8, 9, 10 };
           System.out.println("The Missing number in array3 is: " + getMissingNumber(array3));
       }
    
 }
 
Output

The Missing number in array1 is: 7
The Missing number in array2 is: 10
The Missing number in array3 is: 1



Thanks for feedback.



Read More....
Find the no of islands in a 2D Array/Matrix
3 Sum
4 Sum - Find four elements that sum to a given target value
Chocolate Distribution Problem
Best Time to Buy and Sell Stock