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

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

• javascript
• algorithm

• 3 Possible duplicate of Easy interview question got harder: given numbers 1..100, find the missing number(s) – Paul Hankin Commented Jul 19, 2016 at 23:54
• @PaulHankin I don't think that posting is JavaScript specific. – Jaeeun Lee Commented Jul 20, 2016 at 0:46
• 1 There are several excellent solutions to the problem in pseudo-code. If your question is "what are better algorithms to solve this problem?" then it's a dupe of that question. If your question is "I'm aware of these algorithms, and can someone translate them into javascript for me?" then the question is off-topic. – Paul Hankin Commented Jul 20, 2016 at 1:58
• @PaulHankin I don't think it's off-topic stackoverflow.com/help/on-topic – Jaeeun Lee Commented Jul 20, 2016 at 2:14

8 Answers 8

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.

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]); // output [5, 7, 9, 10, 11]

/* If the starting point is non zero and non one, */

miss = (arr) => {
    let missArr=[];
    let min = Math.min(...arr);
    let max = Math.max(...arr);
    for(i = min; i < max; i++) {
        if(arr.indexOf(i) < 0) {
            missArr.push(i);
        }
    }
    return missArr;
}
miss([6,8,12]); // output [7, 9, 10, 11]

Something like this will do what you want.

    var X = [2, 5, 3, 1, 4, 7, 10, 15]; // Array of numbers
    var N = Array.from(Array(Math.max.apply(Math, X)).keys()); //Generate number array using the largest int from X
    
    Array.prototype.diff = function(a) {
        return this.filter(function(i) {return a.indexOf(i) < 0;}); //Return the difference
    }; 
    console.log(N.diff(X));

Option 1: 
1. create a binary array
2. iterate over input array and for each element mark binary array true.
3. iterate over binary array and find out numbers of false.

Time complexity = O(N)
Space complexity = N

Option 2:
Sort input array O(nLogn)
iterate over sorted array and identify missing number a[i+1]-a[i] > 0
O(n)

total time complexity = O(nlogn) + O(n)

I think the best way to do this without any iterations for a single missing number would be to just use the sum approach.

const arr=[1-100];


let total=n*(n+1)/2;


let totalarray=array.reduce((t,i)=>t+i);

console.log(total-totalarray);

You can try this:

let missingNum= (n) => {
    return n
        .sort((a, b) => a - b)
        .reduce((r, v, i, a) =>
            (l => r.concat(Array.from({ length: v - l - 1 }, _ => ++l)))(a[i - 1]),
            []
        )
}

console.log(missingNum([1,2,3,4,10]));

Solution to find missing numbers from unsorted array or array containing duplicate values.

Array.prototype.max = function() {
  return Math.max.apply(null, this);
};

var array1 = [1, 3, 4, 7, 9];
var n = array1.length;
var totalElements = array1.max(); // Total count including missing numbers. Can use max 
var d = new Uint8Array(totalElements)

for(let i=0; i<n; i++){
	d[array1[i]-1] = 1;
}
var outputArray = [];
for(let i=0; i<totalElements; i++) {
	if(d[i] == 0) {
			outputArray.push(i+1)
	}
}
console.log(outputArray.toString());

My solution uses the same logic as trincot's answer

The time complexity is O(n)

const check_miss = (n) => {
  let temp = Array(Math.max(...n)).fill(0);

  n.forEach((item) => (temp[item] = 1));

  const missing_items = temp
    .map((item, index) => (item === 0 ? index : -1))
    .filter((item) => item !== -1);

  console.log(missing_items);
};

n = [5, 4, 2, 1, 10, 20, 0];
check_miss(n);