Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 1 / c / Solution

The cyclic strict comparisons in the hint identify a head that cannot be the answer:Let $z=a[p]=b[q]=c[r]$ be the smallest common value. The loop invariant is $0\le i\le p<N$, $0\le j\le q<M$, $0\le k\le r<L$, and every discarded entry is not common to all three arrays. If $a[i]<b[j]$, the entry $a[i]$ cannot occur in the unprocessed part of $b$, so discard it. The branch $b[j]<c[k]$ has the analogous justification. If neither comparison holds but the heads are not all equal, the hint guarantees $c[k]<a[i]$, so discard $c[k]$.

A pointer at its target position cannot be advanced: for example $i=p$ and $a[i]<b[j]$ would imply $z<b[j]\le z$. Thus all reads stay within array bounds. The loop variant $(p-i)+(q-j)+(r-k)$ decreases. At exit all heads equal $z$. The cost is $O(N+M+L)$ time and $O(1)$ auxiliary space.