LeetCode Solution 268 - Missing Number

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 the full range is [0,1,2,3]. The missing number is 2.

Example 2:

Input: nums = [0,1]
Output: 2

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Constraints:

• n == nums.length
• 1 <= n <= 10^4
• 0 <= nums[i] <= n
• All the numbers in nums are unique.

---

Optimal Approach: Using Mathematical Summation Formula

Explanation:

The sum of the first n natural numbers is given by the formula:

Sum = n * (n + 1) / 2

By computing the sum of all elements in nums and subtracting it from Sum, we get the missing number.

C++ Implementation:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return total - sum;
    }
};

Time Complexity: O(n), since we traverse nums once.
Space Complexity: O(1), as we use only constant extra space.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Sorting	O(n log n)	O(1)	Sorting adds unnecessary overhead
HashSet	O(n)	O(n)	Requires extra space
XOR Method	O(n)	O(1)	Works well, but summation method is simpler

---

Conclusion

The best approach is the mathematical summation formula because it achieves O(n) time complexity with O(1) space, making it both efficient and memory-friendly.

Related Problems:

• Find Duplicate Number
• First Missing Positive
• Find All Numbers Disappeared in an Array