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.
As the code challenge guarantees that the minimum and maximum are present in the input, you can derive the step from the following info:
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.