Algorithm to check the distance between integers

Question

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

Answer 1

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.

Answer 2

Please have patience with a programmer's view.

For a range (initially the full range) consider the difference between last and first element.

• There is a known minimum up to which no overflow is possible.
• There is a known maximum from which an overflow is always present.
• Between it is unknown, and one may split the range in two lesser and recurse the algorithm.

By recursively splitting the full range in sub-ranges, one should eventually find a violating range, be it an adjacent pair.

Also without recursion, one has a (very) partial function yielding {false, true, unknown}.

The worst case would still be a full iteration.

boolean overflowsDistance(int[] data, int maxDistance) {
    return overflowsDist(data, maxDistance, 0, data.length);
}

// i: start index, j: index after last index.
private boolean overflowsDist(int[] data, int maxDistance, int i, int j) {
    if (i >= j + 1) { // Empty or singleton range
        return false;
    }

    // Heuristic short-cut we hope for:
    int maxAllowable = (j - i) * maxDistance;
    int actual = data[j - 1] - data{[i];
    if (actual > maxAllowable) {
        return false; // There must be an overflow
    }
    // Case monotone integers like [1, 1, 1, 3, 3, 4]:
    if (actual <= maxDistance) { // There cannot be an overflow
        return true;
    }
    // Case distinct integers like [1, 2, 4, 6]:
    if (actual <= maxDistance +  j - i) { // There cannot be an overflow
        return true;
    }

    // Split range:
    int mid = (i + j) / 2;

    return overflowsDist(data, maxDistance, i, mid + 1)
        orelse overflowsDist(data, maxDistance, mid, j);
}

I would not even call the normal behavior O(log N) as an individual overflow is camouflaged by the possibility of having many small increments. Which makes this an interesting programmer's puzzle.