Algorithm to check the distance between integers

MrTeriyaki 08/04/2015. 2 answers, 296 views
algorithms arrays

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

2 Answers


Raphael 08/04/2015.

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.

2 comments
vonbrand 08/05/2015
This sounds wrong... what are "missing elements" here? Surely $a_i$ is always an element of the array.
Raphael♦ 08/06/2015
@vonbrand If you have a subarray [..., i, i+2, ...], then i+1 would be a "missing element". The part above the line answers a variant of the question, which I first though was the question.

Joop Eggen 08/06/2015.

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.

3 comments
2 D.W.♦ 08/05/2015
The original question was "is there a way to solve it without having to iterate around all the array in the worst case?". Can you edit to clarify how this answers the question and what your answer is, and why? Is your answer "No, I can't see any way to solve it without iterating through the entire array in the worst case"?
Joop Eggen 08/06/2015
@D.W. agreed no solution. For any range take the distance between first and last. Below a certain value no overflow, above another value always overflow, between those values unknown. (The unkown cases can recursively apply the algorithm on split ranges.) Just wanted to name the trivial cases and do the algorithm. However I forgot that mathematicians do algorithms better then programmers ;).
Raphael♦ 08/06/2015
I did not (try to) read the code, but I don't understand the idea part before it. Your comment helps, though; if you add in "certain value" and "another value", you should edit that into your answer. (If my impossibility proof is correct, your idea has the worst-case of having to check all subranges.)

Related questions

Hot questions

Language

Popular Tags