public class FindMissing {
public static void main(String[] args) {
int[] arr = {2,4,6,8,12,14,16,18,20,22,24,26};
int val = findMissing(arr, 0, arr.length-1, 2);
System.out.println(val);
}
static int findMissing(int[] arr, int start, int end,int diff) {
if (end >= start) {
int mid = (start + end) / 2;
if (mid<end && (arr[mid+1] - arr[mid]) != diff) {
return arr[mid] + diff;
} else if (mid>0 && (arr[mid] - arr[mid-1]) != diff) {
return arr[mid-1] + diff;
}
//if difference in left and right element of mid are equal to diff then we need to decide to move either //left or right as we will check if our series is correct till mid then we will move to right otherwise left
//for checking till mid series is correct we will use formula : arr[mid]==arr[0]+mid*diff
else if (arr[mid] == arr[0] + mid * diff) {
return findMissing(arr, mid + 1, end, diff);
} else {
return findMissing(arr, start, mid - 1, diff);
}
}
return 0;
}
}
public static void main(String[] args) {
int[] arr = {2,4,6,8,12,14,16,18,20,22,24,26};
int val = findMissing(arr, 0, arr.length-1, 2);
System.out.println(val);
}
static int findMissing(int[] arr, int start, int end,int diff) {
if (end >= start) {
int mid = (start + end) / 2;
if (mid<end && (arr[mid+1] - arr[mid]) != diff) {
return arr[mid] + diff;
} else if (mid>0 && (arr[mid] - arr[mid-1]) != diff) {
return arr[mid-1] + diff;
}
//if difference in left and right element of mid are equal to diff then we need to decide to move either //left or right as we will check if our series is correct till mid then we will move to right otherwise left
//for checking till mid series is correct we will use formula : arr[mid]==arr[0]+mid*diff
else if (arr[mid] == arr[0] + mid * diff) {
return findMissing(arr, mid + 1, end, diff);
} else {
return findMissing(arr, start, mid - 1, diff);
}
}
return 0;
}
}
No comments:
Post a Comment