Find single missing element in sorted an array
class FindSingleMissingElementInAnArray {
static int getMissingElement(int[] array) {
// Corner case
if(array.length == 0) {
System.out.println("Array is empty");
return -1;
}
int sum = 0;
for(int i = 0; i < array.length; i++) {
sum += array[i];
}
int n = array[array.length - 1]; // last element in list
int sumOfNNaturalNumbers = n*(n+1)/2;
return sumOfNNaturalNumbers - sum;
}
static void getMissingElement2(int[] array) {
// Corner case
if(array.length == 0) {
System.out.println("Array is empty");
}
int diff = array[0];
for(int i = 0; i < array.length; i++) {
if(array[i] - i != diff) {
int missingElement = diff + i;
System.out.println("Missing element is : " + missingElement);
break; // don't use break if need to find multiple missing elements
}
}
}
public static void main (String[] args) {
int[] array = new int[] {1,2,3,4,6,7,8,9,10};
System.out.println("Missing element is : " + getMissingElement(array));
getMissingElement2(array);
}
}
Comments
Post a Comment