268. Missing Number

EasyBit ManipulationArrayHash TableMathBinary SearchSorting

Problem Description

You are given an array nums that contains n distinct numbers. These numbers are all from the range [0, n], which means the complete range should have n+1 numbers total (from 0 to n inclusive).

Since the array only contains n numbers but the range has n+1 numbers, exactly one number from the range is missing from the array. Your task is to find and return that missing number.

For example:

If nums = [3, 0, 1], the array has n = 3 numbers from the range [0, 3]. The complete range is {0, 1, 2, 3}. The missing number is 2.
If nums = [0, 1], the array has n = 2 numbers from the range [0, 2]. The complete range is {0, 1, 2}. The missing number is 2.
If nums = [9,6,4,2,3,5,7,0,1], the array has n = 9 numbers from the range [0, 9]. The missing number is 8.

The solution uses XOR bitwise operation to efficiently find the missing number. The key insight is that XOR has two useful properties:

Any number XOR with 0 remains unchanged: x ^ 0 = x
Any number XOR with itself equals 0: x ^ x = 0

By XORing all numbers in the array with all numbers in the complete range [0, n], every number that appears will cancel out (due to x ^ x = 0), leaving only the missing number.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Let's think about this problem step by step. We have an array with n numbers, and we know these numbers should be from the range [0, n]. Since the range has n+1 numbers but our array only has n numbers, one is missing.

The naive approach would be to check each number from 0 to n to see which one is absent. But there's a more elegant way using the XOR operation.

Consider what happens if we had all the numbers from 0 to n, and then we also had a duplicate set of all numbers from 0 to n. If we XOR all these numbers together, we'd get 0 because each number would appear twice, and x ^ x = 0.

Now, what if one number from the second set is missing? When we XOR everything, all pairs would cancel out to 0, except for the one number that doesn't have its pair - that's our missing number!

This is exactly our situation. We can think of it as:

First set: the complete range [0, 1, 2, ..., n]
Second set: our array nums (which is missing one number)

When we XOR all numbers from both sets, every number that exists in both will cancel out, leaving only the missing number.

In the code, enumerate(nums, 1) gives us indices starting from 1, so we're XORing:

Indices: 1, 2, 3, ..., n (which covers part of our complete range)
Array values: the n numbers from our array
The index 0 is implicitly handled since we start from 1

Since XOR is commutative and associative, the order doesn't matter. All the numbers that appear in both the complete range and the array will cancel out, leaving us with the missing number.

Solution Approach

The solution implements the XOR bitwise operation approach to find the missing number efficiently.

The implementation uses Python's reduce function with the XOR operator to accumulate the result of XORing all elements. Here's how it works:

Enumerate with offset: enumerate(nums, 1) generates pairs of (index, value) where the index starts from 1 instead of 0. This means:
- For an array like [3, 0, 1], we get pairs: (1, 3), (2, 0), (3, 1)
XOR each pair: For each pair (i, v), we compute i ^ v. This XORs the index with the corresponding array value.
Reduce with XOR: The reduce(xor, ...) function applies XOR cumulatively across all the i ^ v results. Since XOR is associative, this gives us:
- (1 ^ nums[0]) ^ (2 ^ nums[1]) ^ (3 ^ nums[2]) ^ ...

Let's trace through why this works:

We're XORing the indices [1, 2, 3, ..., n] with the array values
The array contains all numbers from [0, n] except one
After rearranging (since XOR is commutative), we're essentially XORing all numbers from 0 to n, where each appears once, except:
- The missing number appears 0 times
- The number 0 appears once (in the array but not in our indices since we start from 1)
- The number at position of the missing value appears once (as an index)

Due to the XOR properties:

Numbers that appear twice cancel out: x ^ x = 0
The final result is the XOR of numbers appearing an odd number of times

The clever part is that by starting enumeration at 1, we ensure that the missing number will be the only one that appears an odd number of times in the overall XOR operation, making it the final result.

Time Complexity: O(n) - we traverse the array once Space Complexity: O(1) - only using a constant amount of extra space

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with nums = [3, 0, 1]:

Step 1: Identify what we have

Array: [3, 0, 1] with n = 3 numbers
Complete range should be: [0, 1, 2, 3]
Missing number: 2

Step 2: Set up enumeration Using enumerate(nums, 1), we get:

(1, 3) → index 1, value 3
(2, 0) → index 2, value 0
(3, 1) → index 3, value 1

Step 3: XOR each pair For each pair (i, v), compute i ^ v:

1 ^ 3 = 2 (binary: 01 ^ 11 = 10)
2 ^ 0 = 2 (binary: 10 ^ 00 = 10)
3 ^ 1 = 2 (binary: 11 ^ 01 = 10)

Step 4: Reduce with XOR Now XOR all these results together:

First: 2
Then: 2 ^ 2 = 0
Finally: 0 ^ 2 = 2

Result: 2 (our missing number!)

Why this works: Let's rearrange to see the cancellations more clearly. We're effectively XORing:

From indices: 1, 2, 3
From array: 3, 0, 1

Rearranging (since XOR is commutative):

0 ^ 1 ^ 2 ^ 3 (complete range)
^ 3 ^ 0 ^ 1 (array values)

Which becomes:

(0 ^ 0) ^ (1 ^ 1) ^ 2 ^ (3 ^ 3)
= 0 ^ 0 ^ 2 ^ 0
= 2

Every number except 2 appears twice and cancels out, leaving us with the missing number!

Solution Implementation

1from functools import reduce
2from operator import xor
3from typing import List
4
5class Solution:
6    def missingNumber(self, nums: List[int]) -> int:
7        # XOR all indices (starting from 1) with their corresponding values
8        # Since XOR is self-inverse (a ^ a = 0), all matching index-value pairs cancel out
9        # The remaining value is the missing number
10        # Example: nums = [0, 1, 3], indices = [1, 2, 3]
11        # (1 ^ 0) ^ (2 ^ 1) ^ (3 ^ 3) = 1 ^ 2 ^ 0 = 3 (missing number is 2)
12        # Note: enumerate starts from 1 to include n in the XOR operation
13        return reduce(xor, (index ^ value for index, value in enumerate(nums, 1)))
14

1class Solution {
2    public int missingNumber(int[] nums) {
3        // Get the length of the array
4        int n = nums.length;
5      
6        // Initialize result with n (the largest possible missing number)
7        // This handles the edge case where n itself is the missing number
8        int result = n;
9      
10        // XOR all indices and array values
11        // Property: XOR of two identical numbers is 0
12        // We XOR each index i with nums[i] and accumulate in result
13        for (int i = 0; i < n; i++) {
14            // XOR current result with index i and the value at nums[i]
15            // This effectively XORs all numbers from 0 to n with all numbers in the array
16            // The missing number will remain as it appears only once
17            result ^= (i ^ nums[i]);
18        }
19      
20        // Return the missing number
21        // All numbers that appear twice (once in range 0..n and once in array) cancel out
22        // Only the missing number remains
23        return result;
24    }
25}
26

1class Solution {
2public:
3    int missingNumber(vector<int>& nums) {
4        // Get the size of the input array
5        int n = nums.size();
6      
7        // Initialize result with n (the largest possible missing number)
8        // This handles the case where n itself is missing
9        int result = n;
10      
11        // XOR all indices (0 to n-1) and all array elements
12        // The XOR operation will cancel out all numbers that appear twice
13        // (once as an index and once as an array element)
14        // Only the missing number will remain
15        for (int i = 0; i < n; ++i) {
16            result ^= (i ^ nums[i]);
17        }
18      
19        // Return the missing number
20        return result;
21    }
22};
23

1/**
2 * Finds the missing number in an array containing n distinct numbers from 0 to n.
3 * Uses XOR operation to find the missing number efficiently.
4 * 
5 * @param nums - Array of distinct integers from 0 to n with one number missing
6 * @returns The missing number from the range [0, n]
7 */
8function missingNumber(nums: number[]): number {
9    // Get the length of the array (which is n, since one number is missing from 0 to n)
10    const arrayLength: number = nums.length;
11  
12    // Initialize result with n (the length of array)
13    // This handles the case where n itself is the missing number
14    let result: number = arrayLength;
15  
16    // XOR all indices (0 to n-1) and all array elements
17    // XOR properties: a ^ a = 0 and a ^ 0 = a
18    // All numbers that appear both as index and in array will cancel out
19    // Only the missing number will remain
20    for (let index: number = 0; index < arrayLength; index++) {
21        result ^= index ^ nums[index];
22    }
23  
24    // Return the missing number
25    return result;
26}
27

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. This is because the code iterates through all elements in the nums array exactly once using enumerate(), and for each element, it performs a constant-time XOR operation. The reduce() function applies the XOR operation sequentially across all generated values, resulting in a linear pass through the data.

The space complexity is O(1). Despite using a generator expression (i ^ v for i, v in enumerate(nums, 1)), which is lazily evaluated, the reduce() function only maintains a single accumulator value at any given time. The generator doesn't create an intermediate list or array; it yields values one at a time. Therefore, the space usage remains constant regardless of the input size.

Common Pitfalls

Pitfall 1: Misunderstanding the Enumeration Starting Point

The Problem: A common mistake is to use enumerate(nums) (starting from 0) instead of enumerate(nums, 1). This would cause the solution to fail because we wouldn't be XORing with the complete range [0, n].

Incorrect Implementation:

# WRONG - starts enumeration from 0
return reduce(xor, (index ^ value for index, value in enumerate(nums)))

For nums = [3, 0, 1], this would compute:

(0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1) = 3 ^ 1 ^ 3 = 1 (incorrect, should be 2)

Correct Implementation:

# CORRECT - starts enumeration from 1
return reduce(xor, (index ^ value for index, value in enumerate(nums, 1)))

This correctly computes:

(1 ^ 3) ^ (2 ^ 0) ^ (3 ^ 1) = 2 (correct answer)

Pitfall 2: Not Including All Numbers in Range [0, n]

The Problem: Some might try to XOR only the array elements without considering the indices, or forget to include the number n in the XOR operation.

Incorrect Approach:

# WRONG - only XORs array elements
result = 0
for num in nums:
    result ^= num
# This doesn't help find the missing number

Correct Approach: The solution must XOR both the existing numbers AND the complete range [0, n]. By using enumerate(nums, 1), we ensure indices go from 1 to n, and when combined with array values (which contain n numbers from [0, n]), we effectively XOR with all numbers from 0 to n.

Pitfall 3: Alternative Correct Solution Not Recognized

The Confusion: The given solution might seem unintuitive. A clearer alternative that achieves the same result:

def missingNumber(self, nums: List[int]) -> int:
    result = len(nums)  # Start with n
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

This explicitly shows we're XORing:

All indices from 0 to n-1 (through enumerate)
All values in the array
The number n (initial value)

Together, this covers the complete range [0, n], making the logic more transparent.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: