Finding the Missing Number: An Efficient Solution Using Gauss Formula

Today I want to share a coding problem that I recently worked on and found interesting. The problem goes as follows:

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.

At first, I approached this problem by sorting the array and then using a for loop to find the missing number with a time complexity of O(nlogn). (Actually it's O(nlogn + n) but we're simplifying it)

However, after some thought, I realized that there's a simpler and more efficient way to solve it using Gauss formula n(n+1)/2. This formula calculates the sum of integers from 1 to n, which then can be subtracted from the actual sum of the elements in the array to find the missing number!

This brings the time complexity down to O(n)

Here's the code:

function missingNumber(nums: number[]): number {
    let expectedSum: number = (nums.length * (nums.length + 1)) / 2;
    let actualSum: number = 0;

    for (let i = 0; i < nums.length; i++) {
        actualSum += nums[i];
    }

    return expectedSum - actualSum;
};