Skip to content

Instantly share code, notes, and snippets.

@rootid
Created May 25, 2015 12:05
Show Gist options
  • Save rootid/9c346a0e4b012b73efb5 to your computer and use it in GitHub Desktop.
Save rootid/9c346a0e4b012b73efb5 to your computer and use it in GitHub Desktop.
//I/P [1, 2, 4, ,6, 3, 7, 8]
//O/P 5
//NOTE : array is sorted
//1 .total = n*(n+1)/2 leads to overflow if total can't be represented by the number O(n)
//2. XOR (given array) ^ (numbers from 1-n) = missing number O(n)
//3. Binary search (Find out the hole wheather in first half/second half) (O log n)
//Array: [1,2,3,4,5,6,8,9]
//Index: [0,1,2,3,4,5,6,7]
public static int binarySearchHelper(int a[],int start,int end) {
if (start < end) {
int mid = start + (end - start) / 2;
if (a[mid] - a[start] != (mid - start) ) {
//hole is in first half
if (mid - start == 1 && a[mid] - a[start] != 1) {
return mid;
} else {
return binarySearchHelper(a,start,mid-1);
}
} else if (a[end]-a[mid] != (end-mid) ) {
//hole is in second half
if (end - mid == 1 && a[end] - a[mid] != 1) {
return mid;
} else {
return binarySearchHelper(a,mid+1,end);
}
} else {
return -1;
}
} else {
return -1;
}
}
public static int findMissingNumber (int a[]) {
int len = a.length;
return binarySearchHelper (a,0,len);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment