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.
3. Find the difference: Subtract the actual sum from the expected sum. The difference will be the missing number.

Explanation

The solution leverages the mathematical property of arithmetic series. We know the sum of numbers from 0 to n is a predictable value. By comparing this expected sum to the actual sum of the numbers in the input array, we can easily identify the missing number. This method avoids the need for sorting or using extra space (other than a few variables).

Code

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        // Calculate the expected sum of numbers from 0 to n
        int expectedSum = n * (n + 1) / 2;

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

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

Complexity

• Time Complexity: O(n) - We iterate through the array once to calculate the actual sum.
• Space Complexity: O(1) - We only use a few integer variables to store sums and the array length. The space used is constant regardless of the input size.