 Solution

ID: 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 \leq p \leq N + 1

. There are

p

possible values in

[0, p)

but only

k

occurrences of such values in the whole array. When

k < p

Some value in [0, p) is missing.

Repeated 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.

 New to topics? Read the docs here!