Missing Number
FreeBit manipulationEasy74 of 75
The problem
An array of length n contains distinct integers chosen from 0 through n. Find the one value that is absent.
Example
[4, 0, 1, 3] → 2
Need a hint?
XOR cancels values that occur twice.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Initialize an accumulator to n. For every index i, XOR both i and nums[i] into it. Every present value cancels its matching range value, leaving only the missing one. This avoids the overflow risk of adding the whole range in a fixed-width integer.
Complexity
O(n) time and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.