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