CODEWITHSUNDEEP
javascriptarraysalgorithm
Jose
Jose

Reputation: 5200

Return missing number from Array (algorithm)

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?

Upvotes: 2

Views: 1651

Answers (4)

Vedang Mehta
Vedang Mehta

Reputation: 2254

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;
}

Upvotes: 5

Munawir
Munawir

Reputation: 3356

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;
}

Upvotes: 0

David Conrad
David Conrad

Reputation: 16369

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

enter image description here

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;
}

Upvotes: 3

IrkenInvader
IrkenInvader

Reputation: 4050

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;
}

Upvotes: 1

Related Questions