Search Missing Numbers | tech::interview
A sorted array contains integers from 1..n with m of them missing. Find all missing numbers.
Example:
Result has to be
http://www.careercup.com/question?id=5692698000359424
A sorted array contains integers from 1..n with m of them missing. Find all missing numbers.
Example:
n = 8 , m = 2arr = [1,2,4,5,6,8]Result has to be
{3, 7}.http://www.careercup.com/question?id=5692698000359424
def find(a, left, right, result):
if left == right:
return
if left == right - 1:
if a[left] < a[right] - 1:
for i in range(a[left] + 1, a[right]):
result.append(i)
else:
mid = (left + right) / 2
if a[mid] - a[left] > mid - left:
find(a, left, mid, result)
if a[right] - a[mid] > right - mid:
find(a, mid, right, result)