Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 1 / b / i / Solution

Take an integer pivot $0\le p\le N+1$. There are $p$ possible values in $[0,p)$ but only $k$ occurrences of such values in the whole array. When $k<p$, the pigeonhole principle givesRepeated values do not invalidate the argument: they can only reduce the number of distinct values represented by those $k$ occurrences. The other side might also contain a missing value.