Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 2

Let a be the given enclosing array. A two-way array partition needs only one scan, and does not require the pivot to occur in the array:The loop invariant is $l\le k\le j\le r$, every entry of $a[l,k)$ is less than $p$, every entry of $a[k,j)$ is at least $p$, and the segment's multiset is unchanged. Entries outside $[l,r)$ are unchanged. When a(j)<p, swapping it into position k extends the low part; if k<j, the displaced entry was in the high part and remains there after j advances. If k==j, the self-swap is harmless. The other branch simply extends the high part. The loop variant is $r-j$. At exit $j=r$, so the returned $k$ has the required separation property, including empty segments and arbitrarily many duplicate entries. The time complexity is $\Theta (r-l+1)$ and auxiliary space complexity is $O(1)$.

For an integer pivot $0\le p\le N+1$, exactly $k$ entries lie in $[0,p)$. That interval contains $p$ possible integers. If $k<p$, the pigeonhole principle implies that some value in $[0,p)$ is missing. Counting occurrences rather than distinct entries only strengthens this argument: $k$ occurrences cannot cover more than $k$ distinct values.

For completeness, if $p>N+1$ the lower side contains the entire permitted value range, which already has a missing value. If $p\le 0$, the condition $k<p$ is impossible. Thus the general conclusion is a missing permitted value below $p$; an internal pivot gives useful localization.

There are $N-k$ entries in $[p,N+1)$, which contains $N+1-p$ possible integers. If $k\ge p$, then $N-k\le N-p<N+1-p$. Therefore some value in $[p,N+1)$ is missing, again by the pigeonhole principle. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.

If $p\le 0$, the upper side contains the whole permitted range and hence a missing value. If $p>N+1$, the condition $k\ge p$ is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.

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:The precondition is that every original entry lies in $[0,N+1)$. The loop invariant istogether 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\ge p-lo$, while the original active count is strictly less than $hi-lo$; subtraction givesThus 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 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}\le \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: $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)$.