Wednesday, July 13, 2016

find missing item in arithmetic series

- positive integers only.
- first and last are not missing.

Use modded binary search. Check to see if the missing is right before or right after mid.
s m e  m     e
0 1 2  3  4  5
2 4 8 10 12 14

s     m  s  m  e
0 1 2 3  4  5  6
2 4 6 8 10 12 16
(a):
    if a == null || a.length() == 0:
        throw
    missing = -1
    n = a.length()
    delta = (a[n-1] - a[0]) /n
    start = 0, end = n-1
    while start < end:
        mid = start + (end-start)/2
        if a[mid+1] - a[mid] != delta:
            missing = a[mid] +delta
            break
        if mid-1 >= 0 && a[mid] - a[mid-1] != delta:
            missing = a[mid] -delta
            break
        midvalue = a[start] + (mid-start)*delta
        if a[mid] == midvalue:
            start = mid +1
        else:
            end = mid -1
    return missing
[Hat tip to JV]

No comments:

Post a Comment