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

$\qquad\displaystyle
  [a_1, \dots, a_n] \mapsto \begin{cases}
                              \mathrm{true}, &amp;a_n = a_1 + n - 1,\\
                              \mathrm{false}, &amp;\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 &lt; 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 $&lt;n$ of 
the input values. 
Then, $A$ answers false for inputs with $n$ elements of the form

$\qquad\displaystyle 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 \not\in \{1, 2n-1\}$; these cases can be dealt
with similarly. Then, $A$ also answers false on

$\qquad\displaystyle 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.