LeetEye LeetEye
Easy Bit Manipulation ~5 min

Missing Number

bit-manipulation missing-number

Problem

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.

Examples

Example 1
Input: nums = [3,0,1]
Output: 2
Example 2
Input: nums = [0,1]
Output: 2
Example 3
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Key Insight

XOR all numbers 0 to n with all array elements. Pairs cancel, missing number remains.

XOR all indices 0 to n with all array elements. Pairs cancel, missing number survives. Or: n(n+1)/2 - sum(nums).

How to Approach This Problem

Pattern Recognition: When you see keywords like missing number bit-manipulation, think Bit Manipulation.

Step-by-Step Reasoning

1 If we XOR all indices (0 to n) and all elements:
Answer: Both
Each number except missing appears in both index set and array. Missing appears only in index set.
2 For [3, 0, 1], we XOR: Indices: 0, 1, 2, 3 (n=3) Elements: 3, 0, 1
Answer: A and C both work
XOR cancels pairs. Sum difference also works.
3 Expected sum 0+1+...+n = n(n+1)/2. Missing = ?
Answer: expected - actual
Actual sum is missing one number. Difference gives that number.
4 Both XOR and sum methods use:
Answer: O(1) space
Both only need a running accumulator.
5 Sum method might have:
Answer: Integer overflow for large n
n(n+1)/2 can be large. XOR has no overflow issues.

Solution

def missingNumber(nums: List[int]) -> int:
    n = len(nums)
    result = n  # Start with n (last index)
    
    for i in range(n):
        result ^= i ^ nums[i]
    
    return result

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Bit Manipulation problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye