Pattern this teaches:Bit Manipulation
Missing Number
An easy Bit Manipulation interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Bit Manipulation
- Sheets
- 3
- Core for
- 9 roles
The problem
The array has n distinct numbers taken from 0, 1, 2, ..., n, so exactly one number of that range is absent. Find it.
Example 1
- Input
- nums = [2,4,0,1]
- Output
- 3
- Why
- Numbers 0-4 expected, 3 is missing.
Example 2
- Input
- nums = [0, 1]
- Output
- 2
- Why
- The range [0,2] should have 0, 1, 2. The number 2 is missing.
Example 3
- Input
- nums = [5,3,1,4,0]
- Output
- 2
- Why
- Numbers 0-5 expected, 2 is missing.
Constraints
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All numbers in nums are unique
How to think about it
Updated 2026-09-29The complete domain [0, n] and the given array together contain every number twice except for the absent value. If you match each index against its expected item, every present number finds its counterpart. Combining the two sets under an operation that cancels duplicates isolates the unmatched survivor.
Approaches, worst first
Sort and scan discrepancies
time O(n log n) · space O(1)
Sort the array and check whether nums[i] matches index i. If an index mismatches, that index is the missing value; otherwise n is missing. Sort overhead is unneeded here.
Gauss arithmetic summation
time O(n) · space O(1)
Compute the expected total n * (n + 1) / 2 and subtract each element in the array. The remaining difference is the missing number. Highly efficient, though multiplications can risk integer overflow on large constraints in 32-bit systems.
Bitwise XOR cancellationWrite this one
time O(n) · space O(1)
Seed an accumulator with n and XOR every index i and element nums[i] into it. Every number present in both the index set and array cancels out, leaving solely the missing value with zero chance of numeric overflow.
Where people lose marks · 2
- Forgetting to include n itself in the expected range [0, n] causes the algorithm to miss cases where the absent element is the upper boundary n.
- Computing `n * (n + 1)` in standard 32-bit signed integers overflows when n exceeds 46340, making bitwise XOR or 64-bit integers safer across wider numeric domains.
The theory behind it
Bit Manipulation — the ground this problem stands on. All Bit Manipulation problems
What Bit Manipulation is
Bit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How the pattern works
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
More Bit Manipulation problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .