Skip to content

LC 268. Missing Number

mccornet edited this page Jul 25, 2021 · 7 revisions

268. Missing Number

Challenge

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution:

Using math wikipedia to calculate the sum of the first consecutive integers:

  • sum = 1/2 * n * (n+1)

Python

class Solution:

    def missingNumber(self, nums: list[int]) -> int:
        length = len(nums)
        math_sum = (length * (length+1)) // 2
        missing = math_sum - sum(nums)
        return missing

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    // sum of array
    const sum_reducer = (accumulator, currentValue) => accumulator + currentValue;
    const array_sum = nums.reduce(sum_reducer)
    // expected sum = 0.5 * (length * (length+1))
    const length = nums.length
    let consecutive_sum = 0.5 * (length * (length + 1))

    return consecutive_sum - array_sum
};

JavaScript v2

It is also possible to substract each number from the sum instead.

Runtime: 76 ms, faster than 90.48%

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    // expected sum = 0.5 * (length * (length+1))
    const length = nums.length
    let consecutive_sum = 0.5 * (length * (length + 1))

    // remove all numbers present in the array
    for(let i=0; i<length; i++) {
        consecutive_sum -= nums[i]
    }
    
    // only the missing number remains
    return consecutive_sum
};

Clone this wiki locally