Find the Missing Number from sorted array in Java

We have a sorted Array without any repeated number and we have to find missing number.

Example:

Input : 1 2 3 4 6
Output : 5

Example – Program to find the Missing Number from sorted array

n-1 is the length of the array . So the sum of all n elements can be calculated using the formula n*(n+1)/2. Now find the sum of all the elements in the array and subtract it from the sum of first n natural numbers, it will be the value of the missing element.

public class MissingNumber {

  static int getMissingNumber(int a[], int n) {
    int i, total;
    total = (n + 1) * (n + 2) / 2;
    for (i = 0; i < n; i++)
      total -= a[i];
    return total;
  }

  public static void main(String args[]) {
    int array[] = { 1, 2, 3, 4, 6 };
    int missingNum = getMissingNumber(array, array.length);
    System.out.println("Missing number is: " + missingNum);
  }
}

Output

Missing number is: 5

Example – Another way

We go through all the elements. For each element of array a[i], we check if it is equal to i + 1 or not. If not, we return (i + 1).

public class MissingNumber {

  static int getMissingNumber(int a[], int n) {
    for (int i = 0; i < n; i++){
      if (a[i] != (i + 1)){
        return (i + 1);
      }
    }
    return n + 1;
  }

  public static void main(String args[]) {
    int array[] = { 1, 2, 4, 5, 6 };
    int missingNum = getMissingNumber(array, array.length);
    System.out.println("Missing number is: " + missingNum);
  }
}

Output

Missing number is: 3