Missing Number easy

Problem Statement

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.

Example 1:

Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Steps

1. Calculate the expected sum: The sum of numbers from 0 to n is given by the formula n(n+1)/2.
2. Calculate the actual sum: Sum all the numbers present in the input array nums.
3. Find the difference: Subtract the actual sum from the expected sum. The difference will be the missing number.

Explanation

The approach leverages the mathematical property of arithmetic series. We know the expected sum of numbers from 0 to n. By summing the numbers present in the array and subtracting it from the expected sum, we directly obtain the missing number. This avoids the need for sorting or iterating multiple times, leading to a more efficient solution.

Code

function missingNumber(nums: number[]): number {
    // Calculate n (length of the array)
    const n = nums.length;

    // Calculate the expected sum of numbers from 0 to n
    const expectedSum = n * (n + 1) / 2;

    // Calculate the actual sum of numbers in the array
    let actualSum = 0;
    for (let num of nums) {
        actualSum += num;
    }

    // The difference between expected and actual sum is the missing number
    return expectedSum - actualSum;
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once to calculate the actual sum.
• Space Complexity: O(1). We only use a few constant extra variables to store sums and the length of the array. The space used does not depend on the input size.