LeetCode 268: Missing Number

Explanation:

To find the missing number in the array, we can utilize the property of the sum of the first n natural numbers. The sum of the first n natural numbers is given by the formula: n * (n + 1) / 2. By calculating the expected sum of numbers in the range [0, n] and subtracting the sum of the elements in the array, we can find the missing number.

Algorithm:

1. Calculate the expected sum of numbers in the range [0, n] using the formula n * (n + 1) / 2.
2. Calculate the actual sum of elements in the array.
3. Subtract the actual sum from the expected sum to find the missing number.

Time Complexity:

The time complexity of this algorithm is O(n) since we iterate through the array once to calculate the sum.

Space Complexity:

The space complexity of this algorithm is O(1) as we are not using any extra space other than a few variables.

:

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;
    }
}