Return missing number from Array (algorithm)

Question

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?

Sounds like it wants the next number in the sequence if it gives a properly formatted array — IrkenInvader
– 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
– 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
– Jose, Commented May 24, 2016 at 4:47
[1] would return 0 because 0 is missing (it should be the first element) — IrkenInvader
– 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
– Jose, Commented May 24, 2016 at 4:49

Vedang Mehta · Accepted Answer · 2016-05-24 10:46:29Z

5

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

edited May 24, 2016 at 10:46

answered May 24, 2016 at 9:50

Vedang Mehta

2,25211 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

David Conrad · Accepted Answer · 2016-05-24 05:06:54Z

3

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

answered May 24, 2016 at 5:06

David Conrad

16.5k3 gold badges49 silver badges60 bronze badges

Comments

IrkenInvader · Accepted Answer · 2016-05-24 04:50:34Z

1

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

answered May 24, 2016 at 4:50

IrkenInvader

4,0401 gold badge14 silver badges25 bronze badges

4 Comments

David Conrad Over a year ago

It isn't clear from OP's description that the numbers are required to be in any particular order e.g., given the array [2, 4, 0, 1, 5] the answer would be 3, but I may be misreading it.

IrkenInvader Over a year ago

Yeah we weren't sure either! His test cases seem to be leaning in the always start at 0 and count up direction.

Jose Over a year ago

Yeah, unfortunately the test cases aren't made public until you start submitting code but it appears that the array will be given in order by default. Thank you, everyone!

Jose Over a year ago

Actually, now it is throwing unordered arrays. All things considered, the description is not properly explaining the requirements.

Munawir · Accepted Answer · 2016-05-24 05:12:06Z

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

answered May 24, 2016 at 5:12

Munawir

3,3569 gold badges36 silver badges51 bronze badges

3 Comments

Redu Over a year ago

good idea for starters but instead the check should be done like if (i !== nums[i]) return i hence o(n)

Redu Over a year ago

@David Conrad True.. has to sort them first and i guess still will be faster than indexOf method which i think must be o(n^2 / 2) by the way since indexOf won't continue all the way to the end once it finds it's target. It might be safe to assume indexOf running half of the array per search in average.

David Conrad Over a year ago

@Redu constant factors are ignored in big-O analysis, though.

Collectives™ on Stack Overflow

Return missing number from Array (algorithm)

4 Answers 4

Comments

Comments

4 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

4 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related