Here we are going to see the most frequently asked interview question, how to find a missing number in an array sorted/unsorted.

Example
Input: numbers={1,2,3,5,6}
Output: 4
numbers={1,3,2,5,6}
Output: 4

We can find a missing number in an array in different approaches, let’s see the easiest ways.

Find a missing number in an array (Sorted):

Here I am going to show the simplest way to find a missing number in a sorted array.

Approach:

  • Sort an Array using Arrays.sort(arr).
  • Since Array is sorted, we can compare the array indexes with the values.
  • If anyone of the array value not equal to array Index, then we can say that, that is a missed number.
  • Let’s see in practice.
MissingNumber.java
import java.util.Arrays;

public class MissingNumber {

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

    private static Integer getMissingNumber(int[] number) {
        Integer missed = null;
        for (int i = 0; i < number.length; i++) {
            int index = i + 1;
            if (number[i] != index) {
                missed = index;
                break;
            }
        }
        return missed;
    }
}
Output
Missing Number is:5

Find a missing number in an array (Un-Sorted):

We can even find a missing number in an unsorted array in a simple approach using the formula n*(n+1)/2.

Approach:

  • Calculate the sum of number using (n+1) * (n+2)/2
  • Loop through all the elements from the array and subtract all the numbers form the sum.
  • Then you will get the missed number.
MissingNumber.java
public class MissingNumber {

    public static void main(String[] args) {
        int[] number = {6, 3, 2, 4, 1};
        System.out.println("Missing Number is:" + getMissingNumber(number));
    }
    public static int getMissingNumber(int arr[])
    {
        int i, total;
        int n = arr.length;
        total = (n + 1) * (n + 2) / 2;
        for (i = 0; i < n; i++)
            total -= arr[i];
        return total;
    }
}
Output
Missing Number is:5

Happy Learning 🙂

Leave A Comment