C# LeetCode 268: Missing Number - (Easy)

LeetCode 268: Missing Number

This problem gives you an array of distinct numbers ranging from 0 to n, with one number missing. Your task is to find that missing number.
At first, I misread the instructions — I assumed the highest number would be the array's maximum value, not realizing that n is both the length of the array and the upper bound of the range [0, n]. That realisation changed everything for me.

Solution

To solve this, we can use a well-known mathematical formula known as Gauss's formula. It calculates the sum of the first n natural numbers:

Sum = n * (n + 1) / 2

This works because you can pair numbers in the sequence so that each pair adds up to the same value, take the numbers between 1 and 100:

1 + 100 = 101  
2 + 99  = 101  
3 + 98  = 101  
...

n is multiplied by the number of possible pairings (n + 1). Then as we're doing pairings we need to half this number.

So, if the array had no missing number, its sum would match this formula. But since one number is missing, the actual sum of the array will be less than the expected sum.

Thus, the missing number is simply:
Missing = Expected Sum - Actual Sum

Code

public int MissingNumber(int[] nums)
{
    int n = nums.Length;
    int expectedSum = n * (n + 1) / 2;
    int actualSum = 0;

    foreach (int num in nums)
    {
        actualSum += num;
    }

    return expectedSum - actualSum;
}

Example Walkthrough

var numbers = [0, 3, 1];

# sum of all numbers
0 + 3 + 1 = 4

## all numbers added up using Gauss
# 0 -> 3
n = 3
3 * (3 + 1) / 2 = 6

So we can then subtract 6 (Gauss sum) - 4 (actual sum) = 2

So the missing number would be 2.