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)

LeetCode 268: Missing Number

Comments

LeetCode

LeetCode 338: Counting Bits

More from this blog

LeetCode 153. Find Minimum in Rotated Sorted Array

LeetCode 338: Counting Bits

LeetCode 191. Number of 1 Bits

Question

Thought

Core Idea

Method 1: Bit Manipulation (XOR)

Key Properties

Logic Walkthrough

Complexity

Command Palette

Comments

LeetCode

LeetCode 338: Counting Bits

More from this blog

Question

Thought

Core Idea

Method 1: Bit Manipulation (XOR)

Key Properties

Logic Walkthrough

Complexity