Find Missing Numbers from Unsorted Array

Question

I found this JavaScript algorithm excercise:

Question:

From a unsorted array of numbers 1 to 100 excluding one number, how will you find that number?

The solution the author gives is:

function missingNumber(arr) {
    var n = arr.length + 1,
        sum = 0,
        expectedSum = n * (n + 1) / 2;

    for (var i = 0, len = arr.length; i < len; i++) {
        sum += arr[i];
    }

    return expectedSum - sum;
}

I wanted to try and make it so you can find multiple missing numbers.

My solution:

var someArr = [2, 5, 3, 1, 4, 7, 10, 15]

function findMissingNumbers(arr) {
    var missingNumbersCount;
    var missingNumbers = [];
    arr.sort(function(a, b) {
        return a - b;
    })  
    for(var i = 0; i < arr.length; i++) {
        if(arr[i+1] - arr[i] != 1 && arr[i+1] != undefined) {
            missingNumbersCount = arr[i+1] - arr[i] - 1;
            for(j = 1; j <= missingNumbersCount; j++) {
                missingNumbers.push(arr[i] + j)
            }
        }
    }
    return missingNumbers
}

findMissingNumbers(someArr) // [6, 8, 9, 11, 12, 13, 14]

Is there a better way to do this? It has to be JavaScript, since that's what I'm practising.

Answer 1

You could use a sparse array with 1-values at indexes that correspond to values in the input array. Then you could create yet another array with all numbers (with same length as the sparse array), and retain only those values that correspond to an index with a 1-value in the sparse array.

This will run in O(n) time:

function findMissingNumbers(arr) {
    // Create sparse array with a 1 at each index equal to a value in the input.
    var sparse = arr.reduce((sparse, i) => (sparse[i]=1,sparse), []);
    // Create array 0..highest number, and retain only those values for which
    // the sparse array has nothing at that index (and eliminate the 0 value).
    return [...sparse.keys()].filter(i => i && !sparse[i]);
}

var someArr = [2, 5, 3, 1, 4, 7, 10, 15]
var result = findMissingNumbers(someArr);
console.log(result);

NB: this requires EcmaScript2015 support.

Answer 2

The simplest solution to this problem

miss = (arr) => {
    let missArr=[];
    let l = Math.max(...arr);
    let startsWithZero = arr.indexOf(0) > -1 ? 0 : 1;
    for(i = startsWithZero; i < l; i++) {
        if(arr.indexOf(i) < 0) {
            missArr.push(i);
        }
    }
    return missArr;
}
miss([3,4,1,2,6,8,12]);