Missing Number

Share

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, the range is [0,3], and 2 is missing.
Example 2
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation: n = 9, the range is [0,9], and 8 is missing.

Solution Approach

XOR all indices (0 to n) with all values in nums. Numbers that appear in both cancel out (x ^ x = 0), leaving only the missing number (x ^ 0 = x).

  • Start with result = n (the length of the array).
  • For each index i, XOR result with both i and nums[i].
  • Paired values cancel; the missing number is left.
Java
class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
}
Complexity Analysis:

Time complexity: O(n). Single pass through the array.
Space complexity: O(1). Constant extra space.