Finding missing number in unordered arithmetic progression takes too long

Question

I am working on the Code Wars challenge Missing number in Unordered Arithmetic Progression:

If you have not ever heard the term Arithmetic Progression, refer to a previous code challenge:

An Arithmetic Progression is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. [...] There is however one hitch: exactly one term from the original series is missing from the set of numbers which have been given to you. The rest of the given series is the same as the original AP. Find the missing term.

And here is an unordered version. Try if you can survive lists of MASSIVE numbers (which means time limit should be considered). :D

Note: Don't be afraid that the minimum or the maximum element in the list is missing, e.g. [4, 6, 3, 5, 2] is missing 1 or 7, but this case is excluded from the kata (i.e. the code challenge).

Example:

find([3, 9, 1, 11, 13, 5]) # => 7

My solution code works just fine in 99% of test cases. Nevertheless, a random test with big enough input always exceeds the permissible execution time.

function find(seq) {
    function compareNumbers(a, b) {
        return a - b;
    }
    let arr = [...seq].sort(compareNumbers);
    let difference = arr[1]-arr[0];
    let arrLen = arr.length;
    let i=0;
    while(i<arrLen){
        if(arr[i+1]-arr[i]!==difference) return arr[i] + difference;
        i++;
    }
}

I suppose there are some improvements to be made in the sort algorithm or the while loop. I've tried to replace the sort algorithm with a QuickSort one, but that didn't help.

Answer 1

As the code challenge guarantees that the minimum and maximum are present in the input, you can derive the step from the following info:

• minimum
• maximum
• length

Given the minimum and the step, you can easily go through the sequence of expected values and verify they are in the set of input values.

Here is an implementation:

function find(seq) {
    let low = seq[0];
    let high = low;
    for (let i of seq) {
         if (i < low) low = i;
         else if (i > high) high = i;
    }
    let step = (high - low) / seq.length;
    let set = new Set(seq);
    for (let i = low + step; i < high; i += step) {
        if (!set.has(i)) return i;
    }
}

NB: I didn't use Math.min(...seq) here, as for very large arrays that will run into stack size limitations.

Alternative solution

As discussed in comments, we could calculate what the expected sum would be if there were no missing number in the sequence (based on the minimum and maximum in the input, and its length) and subtract the actual sum from that: the difference would be the missing number.

As this sum could be large and even overrun the maximum safe integer for the number data type in JavaScript, we should then shift the input numbers to a "safe" area (around 0) so that the sum will be close to zero. This way we avoid the inaccuracies that would be introduced if the sum would move out of the safe-integer range.

Here is how that looks:

function find(seq) {
    let low = seq[0];
    let high = low;
    for (let i of seq) {
         if (i < low) low = i;
         else if (i > high) high = i;
    }
    let step = (high - low) / seq.length;
    let mid = low + Math.floor((high - low) / 2);
    let expectedSum = (low - mid + high - mid) * (seq.length + 1) / 2;  
    let sum = 0;
    for (let i of seq) {
        sum += i - mid;
    }
    return expectedSum - sum + mid;
}