= Solution
Use <missing-value search by deficient value intervals>: halve the candidate value <interval>, and apply <array partitioning> only to the <array> segment whose entries lie in that <interval>.
``
def missing(): Int = {
require(N < Int.MaxValue)
var lo = 0; var hi = N + 1
var l = 0; var r = N
while (hi - lo > 1) {
val p = lo + (hi - lo) / 2
val k = partition(l, r, p)
if (k - l < p - lo) {
hi = p; r = k
} else {
lo = p; l = k
}
}
lo
}
``
The <loop invariant> is $0\leq l\leq r\leq N$, $0\leq lo<hi\leq N+1$, and
$$
a[l..r)\subseteq[lo,hi),\qquad r-l<hi-lo.
$$
More precisely, the segment contains \b[all occurrences] of original values in $[lo,hi)$, and the complete <array> remains a <permutation> of its original state. The occurrences statement is essential: absence from the final segment must imply absence from the original <array>.
After <array partitioning>, let $m=r-l$, $W=hi-lo$, $m_L=k-l$, and $W_L=p-lo$. If $m_L<W_L$, retain the left side. Otherwise the right side has
$$
m_R=m-m_L<W-W_L=W_R
$$
occurrences. Either choice preserves the strict deficiency and the all-occurrences condition. The positive <integer> width $hi-lo$ decreases, proving termination. At width one, the active segment has fewer than one entry and is empty. Therefore
$$
\boxed{\text{return }lo,\quad lo\in[0,N+1),\quad lo\text{ is absent from the original array}.}
$$
For the <time complexity>, after $t$ splits the width is at most $\lceil(N+1)/2^t\rceil$, and the scan length is smaller than that width. Summing over the $O(\log(N+1))$ levels gives a <geometric series> plus logarithmic overhead, hence $O(N+1)$ overall, conventionally $O(N)$ for $N\geq1$. This proof bounds the retained occurrence count by the retained value width; it does not assume that each <array partitioning> splits the number of occurrences in half. The $N=0$ case returns zero immediately.
Back to article page
