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

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.

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.*

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.)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

- Algorithm to find smallest difference in array
- Algorithm to maximize $j-i$ subject to $A[j]>A[i]$
- Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array
- Algorithm for solving rectangle puzzle
- Algorithm to find the first person in front of $A$ that is shorter than $A$
- recursive algorithm to find the max sum of 2 numbers
- Algorithm with $O(n)$ time and $O(n)$ space to compare two arrays
- Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2?
- How can I use prefix sum of an array to solve this problem?
- Proving the algorithm that orders an array according to the specified positions

- Is there a website that lists the journals that are actually scams?
- Rename chapters to papers
- Cartoon movie where a kid travels to another world
- Why does Mrs Coulter’s hair change colour between La Belle Sauvage and His Dark Materials?
- How to make totally secure Bitcoin transactions?
- "to fart" in child language
- Why should the data be shuffled for machine learning tasks
- I'm looking for a series I read in high school in the 90's about a world where people had one magical ability and words were literal
- Pyramid Scheme Negation
- Is there a name for a voting system that is based on issues rather than people?
- Responding to an unambiguously wrong referee comment
- Why is template argument deduction failing for pointer-to-member-function?
- Why did not Arya kill the Lannister soldiers she encountered in Riverlands?
- Does Doctor Dolittle ever use animals for unusual transport?
- How do you politely stand your ground against authority who repeatedly press a question that you declined to answer?
- Can you reattach an SRAM powerlink?
- Is it possible to fail an ability check on purpose?
- How to reject a proposal from a close friend?
- Expand a number
- I am making a meat stew with wine for the first time, can cooking wine be substituted?
- natas15 blind sql injection
- Why don't we rotate tyres but you rotate tires?
- Skewness of the logarithm of a gamma random variable
- Why do we trust US Certificate Authorities?

`[..., 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 thoughwasthe question.