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
