2
$\begingroup$

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
$\endgroup$
0

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This sounds wrong... what are "missing elements" here? Surely $a_i$ is always an element of the array. $\endgroup$
    – vonbrand
    Aug 5, 2015 at 18:36
  • $\begingroup$ @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. $\endgroup$
    – Raphael
    Aug 6, 2015 at 8:41
0
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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"? $\endgroup$
    – D.W.
    Aug 5, 2015 at 16:40
  • $\begingroup$ @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 ;). $\endgroup$
    – Joop Eggen
    Aug 6, 2015 at 7:50
  • $\begingroup$ 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.) $\endgroup$
    – Raphael
    Aug 6, 2015 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.