= Solution
Keep a deficient interval of possible values and only the <array> segment containing occurrences from that interval. This is <missing-value search by deficient value intervals>:
``
def missing(): Int = {
val n = a.length
var lo = 0L
var hi = n.toLong + 1L
var l = 0
var r = n
while (hi - lo > 1L) {
val p = lo + (hi - lo) / 2L
val k = partition(l, r, p.toInt)
if ((k - l).toLong < p - lo) {
hi = p
r = k
} else {
lo = p
l = k
}
}
lo.toInt
}
``
The <precondition> is that every original entry lies in $[0,N+1)$. The <loop invariant> is
$$
0\leq lo<hi\leq N+1,\qquad 0\leq l\leq r\leq N,\qquad r-l<hi-lo,
$$
together with: every active entry lies in $[lo,hi)$, and every original occurrence with a value in that interval is in the active segment. The whole <array> remains a <permutation> of its initial contents. Initially these assertions follow from the <precondition> and $N<N+1$.
After <array partitioning>, the low subinterval has $k-l$ occurrences and $p-lo$ possible values. If it is deficient, retaining it preserves the <loop invariant>. Otherwise $k-l\geq p-lo$, while the original active count is strictly less than $hi-lo$; subtraction gives
$$
r-k<(hi-lo)-(p-lo)=hi-p.
$$
Thus the high subinterval is deficient and retaining it also preserves the <loop invariant>. Discarded occurrences lie outside the new candidate interval. The <loop variant> is the positive <integer> $hi-lo$, which strictly decreases because the midpoint is strictly internal. At exit the interval has one possible value and fewer than one occurrence, so \b[`lo` is absent from the entire original <array>]. For $N=0$ the loop is skipped and zero is returned. The `Long` value bounds avoid overflowing $N+1$; every internal pivot is at most $N$, so its checked mathematical range fits `Int`.
For the <time complexity>, let $W_i$ be the interval width and $m_i$ its active occurrence count before iteration $i$. The <loop invariant> gives $m_i<W_i$, and <binary search> gives $W_{i+1}\leq\lceil W_i/2\rceil$. Each <two-way array partition> costs $O(m_i+1)$. Until the width reaches one, the widths are bounded by $(N+1)/2^i+1$, so the total scan work is bounded by a <geometric series> plus $O(\log(N+1))$ loop overhead: \b[$O(N+1)$ overall, hence $O(N)$ for positive $N$]. Partitioning the full <array> again at every iteration would instead lose this bound. Auxiliary <space complexity> is $O(1)$.
Back to article page
