Problem Description

The "Missing Number" problem on Leetcode asks you to find the one number that is missing from an array containing n distinct numbers taken from the range 0 to n. The input is an array called nums with n elements, but the numbers are shuffled and one number in the range is missing. You must return the missing number.

• Each number in the range 0 to n appears exactly once, except for the missing number.
• There is exactly one missing number—no duplicates or repeats.
• You cannot reuse elements from the array.
• The array can be in any order.

Example: If nums = [3, 0, 1], then n = 3, and the numbers in the range are 0, 1, 2, 3. The missing number is 2.

Thought Process

To solve this problem, we first think about a brute-force way: for each number between 0 and n, check if it's in the array. This is simple but inefficient, as checking each value in the array can take a long time for large arrays.

Next, we look for patterns or mathematical properties. Since the numbers are supposed to be a complete sequence from 0 to n with one missing, we can use formulas or clever data structures to find the missing value more efficiently.

We also consider whether we can use extra memory, or if we can solve it in-place. For this problem, we can aim for a solution that is both fast and uses minimal extra space.

Solution Approach

There are several ways to solve this problem efficiently. Here are two popular methods:

• 1. Summation Formula:
  • The sum of all numbers from 0 to n is given by the formula n*(n+1)/2.
  • If we sum all numbers in nums and subtract that from the expected sum, we get the missing number.
• 2. XOR Method:
  • XOR all the numbers from 0 to n, and XOR all numbers in nums.
  • Because XORing a number with itself cancels it out, the result will be the missing number.

Both methods run in linear time and use constant extra space. We'll use the summation formula for clarity.

1. Calculate the expected sum of numbers from 0 to n.
2. Calculate the actual sum of the array nums.
3. Subtract the actual sum from the expected sum to get the missing number.

Example Walkthrough

Example Input: nums = [3, 0, 1]

1. Calculate n: The array has 3 elements, so n = 3.
2. Expected sum: n * (n + 1) / 2 = 3 * 4 / 2 = 6.
3. Actual sum: 3 + 0 + 1 = 4.
4. Missing number: 6 - 4 = 2.

Thus, the missing number is 2.

Time and Space Complexity

Brute-force Approach:

• For each number from 0 to n, check if it's in nums (using a loop).
• This is O(n²) time, since for each of n numbers, we may scan the whole array.
• Space is O(1), unless we use a set for lookups, which makes it O(n).

• We scan the array once to compute the sum or XOR, so time complexity is O(n).
• We use a constant number of variables, so space complexity is O(1).

Summary

The "Missing Number" problem is efficiently solved by leveraging mathematical properties of sequences. By comparing the expected sum (or using XOR), we can find the missing value in linear time and constant space. This approach is elegant because it avoids extra data structures and relies on simple arithmetic, making the code both fast and easy to understand.

Code Implementation

class Solution:
    def missingNumber(self, nums):
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum
        

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int expected_sum = n * (n + 1) / 2;
        int actual_sum = 0;
        for (int num : nums) {
            actual_sum += num;
        }
        return expected_sum - actual_sum;
    }
};
        

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

var missingNumber = function(nums) {
    const n = nums.length;
    const expectedSum = n * (n + 1) / 2;
    const actualSum = nums.reduce((a, b) => a + b, 0);
    return expectedSum - actualSum;
};