Wednesday, July 13, 2016

find missing item in arithmetic series

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

Use modded binary search. Converge start and end to the numbers between which the missing number is (i.e. start +1 = end).
s s e        e
0 1 2  3  4  5
2 4 8 10 12 14

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

No comments:

Post a Comment