LeetCode 268: Missing Number

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int result = nums.size();

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

        return result;
    }
};

Question

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.

Thought

This question asks us to find the only missing number, so we can use the XOR ^ bit operation. It means that 0 ^ x = x, x ^ x = 0. Take example 1, for instance, the input nums are 3, 0, 1, and the full numbers are 0, 1, 2, 3.

Therefore, we can XOR all of them: 3^0^1^0^1^2^3 = (3^3) ^ (2) ^ (1^1) ^ (0^0) = 2. As we can see, the answer is 2.

Core Idea

The problem gives us two sets of numbers: the complete range [0, n] and the incomplete input nums. Since only one number is missing, XORing all elements from both sets together will cause every number that appears in both sets to cancel itself out, leaving only the missing number.

Method 1: Bit Manipulation (XOR)

Key Properties

• x ^ x = 0

• x ^ 0 = x

Logic Walkthrough

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

• n: nums.size() is 3

• Complete Range: {0, 1, 2, 3}

• Input nums: {3, 0, 1}

• Combined XOR: (0 ^ 1 ^ 2 ^ 3) ^ (3 ^ 0 ^ 1)

• Rearrange & Cancel: (3 ^ 3) ^ (2) ^ (1 ^ 1) ^ (0 ^ 0) = 2

• The result is the missing number, 2.

Complexity

• Time: O(n)

• Space: O(1)