Missing Number

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.

Example 3:

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

Output: 8

Explanation:

n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Approach: XOR Bit Manipulation (Optimal Solution)

Algorithm

1. XOR all indices 0 through n with every value in nums
2. Every value that appears in nums cancels with its matching index
3. What remains is the missing number

Time & Space Complexity

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - constant extra space

Java Implementation

public class MissingNumber {

    /**
     * Find the missing number in the range [0, n].
     * @param nums Array of distinct numbers from [0, n]
     * @return The missing number
     */
    public static int missingNumber(int[] nums) {
        int result = nums.length;

        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i];
        }

        return result;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {3, 0, 1};
        System.out.println("Input: nums = [3, 0, 1]");
        System.out.println("Output: " + missingNumber(nums1)); // Expected: 2

        int[] nums2 = {0, 1};
        System.out.println("Input: nums = [0, 1]");
        System.out.println("Output: " + missingNumber(nums2)); // Expected: 2

        int[] nums3 = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]");
        System.out.println("Output: " + missingNumber(nums3)); // Expected: 8
    }
}

Alternative Approach: Sum Formula (O(1) Space)

The expected sum of 0 + 1 + ... + n is n * (n + 1) / 2. Subtract the actual sum of nums; the difference is the missing number.

public class MissingNumberSum {

    public static int missingNumber(int[] nums) {
        int n = nums.length;
        int expected = n * (n + 1) / 2;
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        return expected - actual;
    }
}

Example Walkthrough

For nums = [3, 0, 1]:

1. result = 3 (n)
2. i=0: result = 3 ^ 0 ^ 3 = 0
3. i=1: result = 0 ^ 1 ^ 0 = 1
4. i=2: result = 1 ^ 2 ^ 1 = 2

Answer: 2.

Key Points

1. Self-Inverse: Pairs cancel under XOR, leaving the missing value
2. Index as Counterpart: Each index mirrors a value in [0, n]
3. Sum Formula Alternative: expected - actual works with O(1) space but risks overflow for huge n
4. No Sorting or Extra Array: Meets the follow-up constraints
5. Edge Case: A missing n (the largest number) is handled by initializing result to nums.length