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 and Explanation

The most efficient way to solve this problem is using the mathematical property of arithmetic series. The sum of numbers from 0 to n is given by the formula: n * (n + 1) / 2. We can calculate the expected sum and subtract the actual sum of the numbers in the input array. The difference will be the missing number.

Here's a breakdown of the steps:

1. Find n: The size of the input array nums gives us n.
2. Calculate the expected sum: Use the formula n * (n + 1) / 2 to compute the sum of numbers from 0 to n.
3. Calculate the actual sum: Iterate through the nums array and sum its elements.
4. Find the difference: Subtract the actual sum from the expected sum. The result is the missing number.

Code (C++)

#include <vector>
#include <numeric>

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int n = nums.size();
        long long expectedSum = (long long)n * (n + 1) / 2; // Use long long to prevent potential integer overflow
        long long actualSum = std::accumulate(nums.begin(), nums.end(), 0LL); // Use 0LL to initialize as long long
        return (int)(expectedSum - actualSum);
    }
};

Complexity Analysis

• Time Complexity: O(n), due to the single pass through the nums array to calculate the actual sum.
• Space Complexity: O(1), as we only use a few integer variables to store intermediate results. The space used is constant regardless of the input size.