#268 Missing Number
frequently reported atAmazonBloombergNVIDIAMicrosoftGoogleMeta
the problem
In plain words
nums holds n distinct numbers taken from 0, 1, …, n. Exactly one number in that range is missing; return it. Aim for O(n) time and O(1) extra space.
in nums = [3,0,1]
out 2
in nums = [0,1]
out 2
in nums = [9,6,4,2,3,5,7,0,1]
out 8
- n == nums.length
- 1 ≤ n ≤ 10⁴
- 0 ≤ nums[i] ≤ n, all distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternXOR cancellationMath shortcut (closed form)
XOR all indices 0…n together with all values. Every number that is present appears twice and cancels. The missing one appears only once (as an index).
solutions
From brute force to optimal
After sorting, a[i] should equal i; the first mismatch is the gap.
- Sort a copy.
- Return the first i with a[i] ≠ i, else n.
Sorting dominates.
The copy (sort in place for O(log n), but that mutates the input).
class Solution { public int missingNumber(int[] nums) { int[] a = nums.clone(); Arrays.sort(a); for (int i = 0; i < a.length; i++) { if (a[i] != i) return i; // first slot whose value is wrong } return a.length; }}Put everything in a set, then probe 0…n.
- Add all nums to a HashSet.
- Return the first i in 0..n not in the set.
Two linear passes, O(1) average lookups.
The set.
class Solution { public int missingNumber(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int num : nums) seen.add(num); for (int i = 0; i <= nums.length; i++) { if (!seen.contains(i)) return i; } return -1; // unreachable }}x = n ^ (0 ^ nums[0]) ^ (1 ^ nums[1]) ^ …; pairs cancel, the missing number remains.
- x = n (the index that has no slot).
- For each i: x ^= i ^ nums[i].
- Return x.
One pass.
One int.
class Solution { public int missingNumber(int[] nums) { int x = nums.length; // the value n has no index, so start with it for (int i = 0; i < nums.length; i++) { x ^= i ^ nums[i]; // every present number cancels with its index } return x; // only the missing number was XOR-ed in once }}Dry run
Expected sum n(n+1)/2 minus the actual sum.
- expected = n(n+1)/2.
- Subtract every num.
- What remains is the missing value.
One pass.
Two ints. With n ≤ 10⁴ the sum is about 5·10⁷, which fits in an int. For huge n use long or XOR.
class Solution { public int missingNumber(int[] nums) { int n = nums.length; int expected = n * (n + 1) / 2; // n <= 10^4, so this fits in an int int actual = 0; for (int num : nums) actual += num; return expected - actual; }}in the room
How to say it in the interview
talk track
- Offer the Gauss sum first because it is easy to explain. Then mention XOR as the version that can never overflow.
- Say why x starts at n: the indices only go up to n − 1, so n must be added in by hand.
- Show the ladder: O(n log n) sort → O(n) with an O(n) set → O(n) with O(1) space.
traps
- Forgetting that n itself can be the missing number — the sorted scan must return n at the end, and the XOR must start at n.
what they ask next
Follow-ups
Find the Duplicate Number (LC 287)?
Different constraints (read-only array, one value repeated). Use Floyd's cycle detection or binary search on the value range.
Two numbers missing?
XOR everything to get a ^ b, split all values by one set bit of it, and XOR each group (like Single Number III). Or use the sum and the sum of squares as two equations.
before you submit
Edge cases to test
- [0] → 1: n itself can be the missing number.
- [1] → 0: zero can be missing too.
- n = 10,000: the Gauss sum (about 5·10⁷) still fits in an int; XOR can never overflow at all.
practise next
Similar problems
- #41First Missing PositiveHardin Arrays & Strings
- #287Find the Duplicate NumberMediumin Linked Lists
- #136Single NumberEasyin Bits