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. Find the expected sum: Calculate the sum of numbers from 0 to n (where n is the length of the input array). This can be done using 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. The sum of numbers from 0 to n is easily calculated. By comparing this expected sum to the actual sum of the numbers present in the array, we can identify the missing element. This method is efficient because it avoids the need for sorting or complex data structures.

Code:

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }
}

Complexity:

• Time complexity: O(n), as we iterate through the array once to calculate the actual sum.
• Space complexity: O(1), as we only use a few constant extra variables. The space used is independent of the input array's size.