CODEWITHSUNDEEP
javascriptarrays
CharStar
CharStar

Reputation: 427

Find 1, 2, 3 missing numbers in an array of first N natural numbers

Assuming an array is sorted, how would you find 1, 2, and 3 missing numbers in an array of the first N natural numbers?

Again, assuming the array is sorted, the following code will work for returning one value that is missing (due to the return statement)

    function findMissingNumbers(array) {
        for (var i = 0; i < array.length; i++) {
            if (array[i] != (i + 1)) {
                return i + 1;
            }
        }
        return 'no missing numbers found';
    }

    var missingArr = [1, 3, 4, 5, 6, 7];
    console.log(findMissingNumbers(missingArr));

I have seen many responses that do the same (find one missing value) by taking the sum and the expected sum and finding the missing value by subtracting the sum from the expected sum however, this too will only find one missing value.

I know that this code will not work by using i as I am-- I tried to write it by pushing the missing values into a new array if arr[i] != i + 1, but again, this will only return the correct value for the first missing value.

How would you approach this problem?

Upvotes: 3

Views: 2127

Answers (6)

Dexygen
Dexygen

Reputation: 12561

Here is an(other) non-ES6 solution. The inner loop could probably be reworked to not require sorting as the next to last line.

Regardless of the inner loop it should at worst run in O(n) x 2 vis a vis an array bounded by 1 and the max value of the array -- the inner loop is only run more than once to find more than one "gaps".

Maybe the loop is less elegant than this non-ES6 implementation, but on the other hand mine has the advantage of not introducing any variables other than the array that gets returned.

function findMissingNumbers(array) {
    var missingNumbers = [];

    for (var i=0, n=array.length; i<n; i++) {
        if (array[i] > (i + 1 + missingNumbers.length)) {
            for (j=1, k = array[i] - (i + 1 + missingNumbers.length); j<=k; j++) {
                missingNumbers.push(array[i] - j);
            }
        }
    }

    missingNumbers.sort();
    return missingNumbers;
}

var missingArr = [1, 4, 5, 6, 7, 9];
console.log(findMissingNumbers(missingArr).join(",")); //2,3,8

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386654

You could use Set

function* findMissingNumbers(array) {
    var numbers = new Set(array),
        i = 1;

    while (numbers.size) {
        if (numbers.has(i)) {
            numbers.delete(i);
        } else {
            yield i;
        }
        i++;
    }
}

console.log([...findMissingNumbers([1, 3, 4, 5, 6, 7])]);
console.log([...findMissingNumbers([6, 7])]);
console.log([...findMissingNumbers([1, 2, 3, 4, 5, 6, 7])]);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 0

guest271314
guest271314

Reputation: 1

You can use Array.prototype.reduce(), do..while loop

var missingArr = [1, 3, 4, 5, 6, 7, 9];
var res = [];

missingArr.reduce(function(a, b) {
  var i = a + 1;
  if (i !== b) {
    do { 
      res.push(i++) 
    } while (i < b);
  }
  return b
});

console.log(res);

Upvotes: 1

My Stack Overfloweth
My Stack Overfloweth

Reputation: 4944

You'll need to make two changes here.

  1. Returning an array from your function instead of returning the number within the first iteration of your for loop.
  2. Create a new variable to keep track of those numbers that have been missed.

Below is the updated code snippet:

function findMissingNumbers(array) {
    var resultsArray = [];
    var missedNumbers = 0;

    for (var i = 0; i < array.length; i++) {
        var expectedValue = i + 1 + missedNumbers;

        if (array[i] != expectedValue) {
            var segmentCountOfMissedNumbers = array[i] - expectedValue;

            for (var ii = 0; ii < segmentCountOfMissedNumbers; ii++) {
                resultsArray.push(expectedValue + ii);
            }
            missedNumbers = missedNumbers + segmentCountOfMissedNumbers;
        }
    }

    if (resultsArray.length > 0) {
        return resultsArray;
    } else {
        return 'no missing numbers found';
    }
}

var missingArr = [3, 5, 9];
console.log(findMissingNumbers(missingArr));

Upvotes: 1

Abhinav Galodha
Abhinav Galodha

Reputation: 9878

One more implementation that should work. It should be O(n) in terms of time complexity.

function findMissingNumbers(array) {
	    var missingNumbers = [];
	    var endInteger = array[array.length - 1];
		var missingNumberCounter = 0;
		
        for (var i=0; i < endInteger; i++) {
            if (array[i - missingNumberCounter] != (i + 1)) {
                missingNumbers.push(i + 1);
		missingNumberCounter++;
            }
        }
        return missingNumbers;
        
    }

var missingArr = [1, 3, 4, 5, 6, 7];
var missingArr2 = [2, 3, 4, 9, 10, 11];
console.log(findMissingNumbers(missingArr));
console.log(findMissingNumbers(missingArr2));

Upvotes: 3

Nenad Vracar
Nenad Vracar

Reputation: 122057

Find minimum and maxium number in array, create array from them using Array.from() filter that array with provided array to return missing numbers.

 function findMissingNumbers(arr) {
  var min = Math.min(...arr);
  var max = Math.max(...arr);
  var all = Array.from(Array(max - min + 1), (e, i) => i + min)
  return all.filter(e => !arr.includes(e))
 }

 console.log(findMissingNumbers([1, 3, 4, 5, 6, 7]));
  console.log(findMissingNumbers([10, 16, 8]));

Upvotes: 4

Related Questions