268.md

268. Missing Number

Description

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.

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution

Solution 1

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    "use strict";
    let sum = nums.length * (1 + nums.length) / 2;
    for (let i = 0; i < nums.length; i++) {
        sum -= nums[i];
    }
    return sum;
};

Solution 2

/**
 * Solved with bit manipulation (XOR)
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    "use strict";
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        result ^= (i ^ nums[i]);
    }
    result ^= (nums.length);
    return result;
};