= Solution
The cyclic strict comparisons in the hint identify a head that cannot be the answer:
``
PROCEDURE common3(a, N, b, M, c, L): INTEGER;
VAR i, j, k: INTEGER;
BEGIN
i := 0; j := 0; k := 0;
WHILE (a[i] # b[j]) OR (b[j] # c[k]) DO
IF a[i] < b[j] THEN i := i + 1
ELSIF b[j] < c[k] THEN j := j + 1
ELSE k := k + 1
END
END;
RETURN a[i]
END common3;
``
Let $z=a[p]=b[q]=c[r]$ be the smallest common value. The <loop invariant> is $0\leq i\leq p<N$, $0\leq j\leq q<M$, $0\leq k\leq 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]\leq z$. Thus all reads stay within <array bounds>. The <loop variant> $(p-i)+(q-j)+(r-k)$ decreases. At exit all heads equal $z$. \b[The cost is $O(N+M+L)$ time and $O(1)$ auxiliary space.]
Back to article page
