You are given a sorted number list from 0 to n. The list is missing one number, find out that number
Approach:We can run a binary search. Check the value in the middle, and see if the index of it is same as the value. If it is not, then 0 to mid range has a missing number, search in that range. Otherwise search in the range mid+1 to n. Continue similarly reducing the range by half every time, until you find the missing number.
#include <iostream> using namespace std; int findMissing(int *input, int len) { int start = 0, end = len; while (start < len) { int mid = (start+end)/2; if (input[mid] == mid ) { if (input[mid+1] != mid+1) return mid+1; start = mid+1; } else { if (input[mid-1] != mid-1) return mid-1; end = mid; } } return -1; } const int MAX_LEN = 15; int main() { int input[MAX_LEN] = {0,1,2,3,4,5,6,7,8,9,10,12,13,14,15}; cout << "Missing number: " << findMissing(input,MAX_LEN) << endl; return 0; }Output:-
Missing number: 11
0 comments:
Post a Comment