Missing Number Explained

Problem Statement

Given an array nums containing n distinct integers in the range [0, n], find the one integer in the range that is missing from the array. The solution should use O(1) extra space and O(n) time complexity. This problem tests your ability to use bitwise XOR or arithmetic to identify the missing element efficiently.

Example

Input: nums = [3,0,1]

Output: 2

Explanation: The range [0, 3] includes 0, 1, 2, 3, but 2 is missing from the array.

Code

public class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result ^= i;
            result ^= nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 0, 1};
        System.out.println(sol.missingNumber(nums)); // 2
    }
}
            

def missing_number(nums):
    result = len(nums)
    for i in range(len(nums)):
        result ^= i
        result ^= nums[i]
    return result

# Example usage
print(missing_number([3, 0, 1]))  # 2
            

function missingNumber(nums) {
    let result = nums.length;
    for (let i = 0; i < nums.length; i++) {
        result ^= i;
        result ^= nums[i];
    }
    return result;
}

// Example usage
console.log(missingNumber([3, 0, 1])); // 2
            

Explanation

• Initialize result to n, the length of the array.
• For each index i, XOR result with both i and nums[i].
• This effectively XORs all numbers from 0 to n with the array elements.
• Numbers present in both cancel out (XOR with themselves is 0).
• The missing number remains as the final result.

Note