Algorithm to find missing number in arithmetic progression, Here we are going to use binary search to get missing number in O(logn) time
Input : int a[] = { 1, 2, 3, 4, 6, 7, 8, 9, 10 };
Output : 5
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
public class FindMissingNumberInAP { public static void main(String args[]) { int a[] = { 1, 2, 3, 4, 6, 7, 8, 9, 10 }; System.out.println(findMissingNumberInAP(a, a.length)); a[] = {2,4,6,8,10,14,16,18,20}; System.out.println(findMissingNumberInAP(a, a.length)); } public static int findMissingNumberInAP(int a[], int size) { int diff = Math.min((a[1] - a[0]), (a[2] - a[1])); int missing = -1; int start = 0; int end = size - 1; while (start <= end) { int middle = (start + end) / 2; int whatIsThereAtMiddle = a[middle]; int whatShouldBeThereAtMiddle = a[0] + middle * diff;// IMP line if (whatIsThereAtMiddle == whatShouldBeThereAtMiddle) { start = middle + 1; } else { missing = whatShouldBeThereAtMiddle; end = middle - 1; } } return missing; } } |