# 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