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

HighResolutionMusic.com - Download Hi-Res Songs

1 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
2 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
3 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
4 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
7 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
8 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
9 Brooks

Limbo flac

Brooks. 2018.
10 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
11 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
12 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
13 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
14 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
15 Billie Eilish

When The Party's Over flac

Billie Eilish. 2018. Writer: Billie Eilish;FINNEAS.
16 K-391

Mystery flac

K-391. 2018.
17 Cher Lloyd

None Of My Business flac

Cher Lloyd. 2018. Writer: ​iamBADDLUCK;Alexsej Vlasenko;Kate Morgan;Henrik Meinke;Jonas Kalisch;Jeremy Chacon.
18 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
19 Lil Pump

Arms Around You flac

Lil Pump. 2018. Writer: Rio Santana;Lil Pump;Edgar Barrera;Mally Mall;Jon Fx;Skrillex;Maluma;Swae Lee;XXXTENTACION.
20 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.

Related questions

Hot questions

Language

Popular Tags