Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Algorithm to check the distance between integers

, ,
Problem Detail:

I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case.

I have a sorted array of pairwise distinct integers, say $[1,2,4,5,7,8]$ I need to know if there is a gap of at least two between two consecutive integers, i.e., if there are successive integers $a$ and $b$ in the list with $b>a+2$.

For example in the array given, the algorithm should return false, but for $[2,3,6,7]$, it should return true. Is it possible to solve it by mathematics instead of iterate and compare the integers one by one?

I will add some inputs and the desired output:

• [1,2,4] -> false
• [1,2,5] -> true
• [1,2,4,6,8] -> false
• [1,3,4,6,8] -> false
• [1,4,6,8] -> true
• [1,3,5] -> false

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}, &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

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

Question Source : http://cs.stackexchange.com/questions/45005