I'm working on an algorithm problem (on leetcode) which is asking the following:

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

My current answer is:

var missingNumber = function(nums) {
  return nums.filter(function(item, index, arr) {
    return arr[index] - arr[index - 1] > 1;
  }).shift() - 1; 
};

However, leetcode is using these two test cases (among some others) which make no sense to me:

Input: [0] Expected: 1

Input: [0, 1] Expected: 2

EDIT: also...

Input: [1] Expected: 0

From what I understand, the algorithm is asking to return a single number that is missing from an array, given there is a number that is actually missing in the first place. Am I missing something here or are the instructions for this algorithm very unclear?

I'm working on an algorithm problem (on leetcode) which is asking the following:

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example, Given nums = [0, 1, 3] return 2.

My current answer is:

var missingNumber = function(nums) {
  return nums.filter(function(item, index, arr) {
    return arr[index] - arr[index - 1] > 1;
  }).shift() - 1; 
};

However, leetcode is using these two test cases (among some others) which make no sense to me:

Input: [0] Expected: 1

Input: [0, 1] Expected: 2

EDIT: also...

Input: [1] Expected: 0

From what I understand, the algorithm is asking to return a single number that is missing from an array, given there is a number that is actually missing in the first place. Am I missing something here or are the instructions for this algorithm very unclear?

• javascript
• arrays
• algorithm

• Sounds like it wants the next number in the sequence if it gives a properly formatted array – IrkenInvader Commented May 24, 2016 at 4:45
• I think they simply want to count from 0 until arr.length+1, and return on the first that you don't find in the array where you expected it. – Bergi Commented May 24, 2016 at 4:46
• @IrkenInvader: I see, that would explain the test cases. Although it also expects [1] to return 0. I'll edit my description. – Jose Commented May 24, 2016 at 4:47
• [1] would return 0 because 0 is missing (it should be the first element) – IrkenInvader Commented May 24, 2016 at 4:47
• That makes more sense. I think that could be explained a bit clearer, but perhaps it's my mistake. – Jose Commented May 24, 2016 at 4:49

4 Answers 4

There is a different way to do it using XOR operation. The idea here is that a number XORed with itself will always be 0. We can store XORs of all the numbers from 0 to N in variable xor1 and XORs of all the numbers of our array in variable xor2. The XOR of xor1 and xor2 will be the missing number as it will only appear in xor1 and not in xor2.

function foo(arr){
        var n = arr.length;
        var xor1 = 0, xor2 = 0;
        for(var i = 0;i <= n;i++)
                xor1 ^= i;
        for(var i = 0;i < n;i++)
                xor2 ^= arr[i];
        return xor1 ^ xor2;
}

The total of the integers from 1..n is:

So, the expected total of an array of length n with values from 0..n would be the same. The missing number would be the total minus the sum of the actual values in the array:

"use strict";
let missingNumber = function(nums) {
    let n = nums.length;
    let expected = n * (n + 1) / 2;
    let total = nums.reduce((a, b) => a + b, 0);
    return expected - total;
}

This is how I would implement it, you can loop until <= to the array length so if the passed in array passes the test it will try to look at nums[nums.length] which will be undefined and return i correctly. Return 0 if they pass in an empty array.

var missingNumber = function(nums){
  for(var i = 0; i <= nums.length; i++){
    if(nums[i] !== i) return i;
  }
  return 0;
}

Try using indexOf() method. It returns -1 if the item is not found.

nums = [0, 1, 3];
var missingNumber = function(nums){
  for(i = 0; i <= nums.length; i++){
    if(nums.indexOf(i) < 0 ) {
      return i;
    }
  }
  return 0;
}