1

I have a Long array with these numbers:

long[] = {1,2,3,5,6,7};

Notice that 4 is missing. What's the best way to test this array if any such gaps exist or not?

Madhawa Priyashantha
  • 9,633
  • 7
  • 33
  • 60
goe
  • 1,153
  • 2
  • 12
  • 24
  • 1
    Go through the array and check if the previous number is smaller than `current-1`? – Kayaman May 05 '15 at 12:46
  • iterate over all of them, and check that i == element (+x). (if duplicates are possible, you'll need to consider those as well) – Stultuske May 05 '15 at 12:46
  • 3
    Are elements guaranteed to be ordered? Also are they unique? – Pshemo May 05 '15 at 12:48
  • I could create a website dedicated to all the wrong answers that keep showing up. –  May 05 '15 at 13:00
  • 1
    I'm not going to supply the code, but just suggest looping through looking to make sure that any given element is 1 more than the prior element (with an immediate pass for empty or arrays of size 1). But again, we need clarification on some of the rules here. –  May 05 '15 at 13:03
  • I believe QBrute's ***revised*** answer is now the fastest, so long as the array is increasing and sorted. He needs to put in checks for null and empty arrays too. This question is too vague. –  May 05 '15 at 13:16

4 Answers4

5

If you're guaranteed that arrays is ordered without any duplicate then you could check that in O(1)

I think this code should work in this specific case :)

//assume that given array is ordered and has no duplicated value
long[] myarray = {5,6,7};                 //no gap
long[] myarray1 = {1,2,4};                //has gap
long[] myarray2 = {10,11,12,13,14,15};    //no gap

//return true if has gap
//return false if no gap
//throw null-pointer if empty
public static boolean checkIfHasGap(long[] array) {
    if (array.length == 0) {
        throw new NullPointerException("Given Array is empty");
    } else {
        return array[0] + array.length != array[array.length - 1] + 1;
    }
}
Chhorn Elit
  • 5,038
  • 1
  • 12
  • 14
Xorr
  • 86
  • 1
  • 5
  • 1
    `array.length == 2` should not be a separate case. The first case should be `array.length == 0` (cannot be negative, and 1 is also covered by the last case). Otherwise +1, this is `O(1)` answer. – gaborsch May 05 '15 at 14:12
0

Loop through the array and check, if the current item is exactly x more than the current index, where x is the first element in your array.

public boolean hasGaps(long[] array) {
    if(array == null || array.length == 0) {
        return false;
    }

    long start = array[0];
    for(int i = 0; i < array.length; i++) {
        if(array[i] != i + start) {
            return true;
        }
    }
    return false;
}
QBrute
  • 4,405
  • 6
  • 34
  • 40
  • 1
    HAHA, no. This fails for {2} –  May 05 '15 at 12:59
  • and btw. OP states, that he wants a solution for his concrete array. So my first answer was correct for that special case. – QBrute May 05 '15 at 13:07
  • No, because for that "concrete" array, the answer would be to look at it. He's clearly looking for a general purpose algorithm. –  May 05 '15 at 13:08
  • You should probably make sure that the array isn't empty, or null. –  May 05 '15 at 13:17
  • To be clear, for this algorithm we need to make sure 1. that the array is increasing, and 2. that it's ordered. –  May 05 '15 at 13:19
0
public static boolean hasGaps(long[] array) {
    if (array == null || array.length == 0) {
        return false;
    }
    if (array[array.length - 1] - array[0] + 1 != array.length) {
        return true;
    }
    for (int i = 1; i < array.length; i++) {
        if (array[i] != array[i - 1] + 1) {
            return true;
        }
    }
    return false;
}

This method first check for the "easy" cases, then iterate the array to check the more complex cases.

Florent Bayle
  • 11,520
  • 4
  • 34
  • 47
0

A simpler and reliable way:

const getMissingNumbers = (list) => {
  if (!list || list.length === 0) return [];

  const missing = [];
  // sort the list
  list.sort((a, b) => a - b);
  // pin start and end points in the list
  const step = list[0];
  const last = list[list.length - 1];
  for (let i = step; i < last; i++) {
    if (list.indexOf(i) === -1) missing.push(i);
  }
  return missing;
}
zapalote
  • 43
  • 1
  • 6