[Solved]: Algorithm to check the distance between integers

If you allow no missing elements, there is indeed an algorithm that does not need to check all values: Since the numbers are distinct and sorted, the algorithm $qquaddisplaystyle [a_1, dots, a_n] mapsto begin{cases} mathrm{true}, &a_n = a_1 + n – 1, mathrm{false}, &text{else} end{cases}$ solves the problem. If $a_n geq a_1 + n$ there has to be a step larger than one. On the other hand, $a_n < a_1 + n – 1$ can not happen without duplicates (pigeon-hole principle). If you allow some missing elements but not too many in a row, this no longer works. We will show this by an adversary argument. Assume there was a deterministic, correct algorithm $A$ that reads $<n$ of the input values. Then, $A$ answers false for inputs with $n$ elements of the form $qquaddisplaystyle I_1 = [1,3,dots,2n-1]$. By assumption, $A$ does not read at least one value; let’s call that one $i$. Without loss of generality, let $i notin {1, 2n-1}$; these cases can be dealt with similarly. Then, $A$ also answers false on $qquaddisplaystyle I_2 = [1,dots,i-2,mathbf{i+1},i+2,dots,2n-1]$ because it is deterministic; if it does not read $i$ on $I_1$ it will also not read $i+1$ on $I_2$ since the other elements are all the same. But this result is wrong since there is a gap of $(i+1) – (i-2) = 3$ in $I_2$. This contradicts our assumption that $A$ is correct; therefore, there can be no such algorithm.