Missing Number LeetCode 268 Deep Dive

LeetCode 268 — Missing Number — gives you an array nums of n distinct integers where each integer is in the range [0, n] inclusive. Because there are n+1 possible values (0 through n) but only n slots in the array, exactly one value must be absent. Your task is to find and return that missing value. For example, nums = [3, 0, 1] has n = 3, the range is [0, 3], and the value 2 is missing, so the answer is 2.

The problem is rated Easy on LeetCode and appears in the Top Interview 150 list. Despite the Easy label, it rewards knowledge of multiple algorithmic techniques: arithmetic series formulas, XOR bit manipulation, and sorting. A brute-force approach using a hash set to track seen numbers would work in O(n) time but uses O(n) extra space. The challenge for interviewers is to ask for O(1) extra space, which rules out the hash set and forces a more mathematical solution.

LeetCode 268 is a companion to other bit manipulation problems such as LeetCode 136 (Single Number), LeetCode 191 (Number of 1 Bits), and LeetCode 338 (Counting Bits). The XOR technique used here is essentially the same self-cancellation trick from Single Number, applied with indices rather than a second copy of the array.

The Gauss sum approach exploits the closed-form formula for the sum of the first n non-negative integers: expected = n * (n + 1) / 2. This formula — attributed to Carl Friedrich Gauss — gives the sum 0 + 1 + 2 + ... + n instantly in O(1) time without a loop. Once you have the expected total, computing the actual sum of the array elements takes one O(n) pass. The missing number is simply expected minus actual.

For nums = [3, 0, 1] with n = 3: expected = 3 * 4 / 2 = 6. Actual sum = 3 + 0 + 1 = 4. Missing = 6 - 4 = 2. Correct. For nums = [0, 1] with n = 2: expected = 2 * 3 / 2 = 3. Actual = 0 + 1 = 1. Missing = 3 - 1 = 2. The approach always works because the range [0, n] contains every integer exactly once, so the difference between the complete sum and the partial sum is the single missing element.

The Gauss sum approach runs in O(n) time and O(1) space. Its one potential weakness is integer overflow: for languages with fixed-width integers (Java int, C++ int), n * (n + 1) could overflow if n is large. In practice, LeetCode 268 constrains n to at most 10^4, so overflow does not occur with 32-bit integers. But in general interviews it is worth mentioning the XOR alternative as an overflow-safe option.

The XOR approach initializes a variable missing = n, then iterates over every index i from 0 to n-1 and XORs in both i and nums[i]. After the loop, missing holds the answer. This works because every value that is present in the array appears twice in the XOR chain — once as an index and once as an array value — and a XOR a = 0, so all present pairs cancel out. The only value that appears exactly once is the missing number, which is XOR-ed in only as an index (via the range 0..n) but never as an array value. That unpaired value survives and is returned.

For nums = [3, 0, 1] with n = 3: start missing = 3. i=0: missing ^= 0 ^= 3 → 3^0^3 = 0. i=1: missing ^= 1 ^= 0 → 0^1^0 = 1. i=2: missing ^= 2 ^= 1 → 1^2^1 = 2. Final missing = 2. Correct. Each present value (0, 1, 3) appears in both the index sequence and the array, so it cancels. Value 2 appears only in the index sequence (as i=2) and never in the array, so it remains.

XOR avoids arithmetic overflow entirely because bitwise operations do not carry across a word boundary in the overflow sense. It runs in O(n) time and O(1) space, matching the Gauss approach on complexity while being strictly safer for large integers. The tradeoff is readability: the XOR approach requires understanding why self-cancellation works, whereas the sum approach is immediately intuitive to anyone who recognizes the Gauss formula.

XOR has three algebraic properties that make this technique possible. First, a XOR a = 0: any value XOR-ed with itself equals zero. Second, a XOR 0 = a: XOR-ing with zero is a no-op that preserves the value. Third, XOR is both commutative (a ^ b = b ^ a) and associative ((a ^ b) ^ c = a ^ (b ^ c)), so the order in which we XOR values does not matter. Together these properties mean that if you XOR a multiset of integers where every value appears an even number of times except one, the result is the one value with an odd count.

In the missing number problem, we construct a multiset containing all indices 0..n (that is n+1 values) and all array elements (n values). Every integer from 0 to n that is present in the array appears exactly twice — once as an index and once as an array element — so it cancels to 0. The missing integer appears exactly once — only as an index, never as an array element — so it does not cancel and survives as the final XOR result.

This same XOR cancellation technique solves LeetCode 136 (Single Number), where every element appears twice except one: XOR-ing all elements leaves the singleton. The missing number problem is structurally identical, just with the "second copy" of each present value coming from the index range rather than a duplicate in the array. Recognizing this structural similarity is the insight that allows you to transfer the Single Number solution directly to Missing Number.

The sorting approach is the simplest conceptually: sort the array, then scan from left to right looking for the first position i where nums[i] != i. That index i is the missing number. If no such position exists after scanning all n elements, then the missing number is n itself (the last value in the range). For example, sorting [3, 0, 1] gives [0, 1, 3]. At i=0: 0 == 0, ok. At i=1: 1 == 1, ok. At i=2: 3 != 2, so the answer is 2.

The sorting approach runs in O(n log n) time due to the sort, and O(1) extra space if you sort in place (using an in-place sort like heapsort). It is not optimal — the Gauss and XOR approaches both achieve O(n) time — but it is a valid and easy-to-explain solution. In an interview it is a reasonable starting point before optimizing, demonstrating that you can always fall back to a simpler approach when the optimal trick is not immediately obvious.

One edge case to handle: if the sorted array is exactly [0, 1, 2, ..., n-1] (no early mismatch), the missing number is n. This happens when the array contains 0 through n-1 and is missing n. Make sure to return n after the loop completes without finding a mismatch. This edge case is easy to miss when coding quickly under pressure.

Python — Gauss sum (one-liner): def missingNumber(self, nums): n = len(nums); return n*(n+1)//2 - sum(nums). Python integers have arbitrary precision so overflow is not an issue. Python — XOR version: def missingNumber(self, nums): missing = len(nums); [missing := missing ^ i ^ v for i, v in enumerate(nums)]; return missing. Or more readably: missing = len(nums); for i, v in enumerate(nums): missing ^= i ^ v; return missing. Both are O(n) time O(1) space. The XOR version works identically whether n is 10 or 10^9 — no special handling needed.

Java — Gauss sum: public int missingNumber(int[] nums) { int n = nums.length; int expected = n * (n + 1) / 2; int actual = 0; for (int v : nums) actual += v; return expected - actual; }. Java — XOR version: public int missingNumber(int[] nums) { int missing = nums.length; for (int i = 0; i < nums.length; i++) missing ^= i ^ nums[i]; return missing; }. The XOR version is preferred in Java because n*(n+1)/2 can overflow a 32-bit int for large n (though LeetCode 268 constraints keep n small enough). Both are O(n) time O(1) space.

When presenting in an interview, lead with the Gauss sum — it is immediately readable and demonstrates mathematical fluency. Then offer the XOR version as the overflow-safe alternative and explain the cancellation logic. Mentioning both approaches and their tradeoffs (readability vs. overflow safety) is the ideal interview answer. The sorting approach is worth mentioning as the simplest baseline but explicitly noting it is O(n log n) and therefore suboptimal.

Single Number (LeetCode 136) is the closest sibling: XOR all elements and the one value appearing an odd number of times survives. Missing Number uses the same cancellation but the "second copy" of each present value comes from the index range 0..n rather than a duplicate in the array. Once you understand LeetCode 136 deeply, LeetCode 268 becomes a straightforward structural extension. Both problems are in the LeetCode bit manipulation study plan.

Counting Bits (LeetCode 338) and Number of 1 Bits (LeetCode 191) form the broader bit manipulation family. LeetCode 191 counts set bits in a single integer using Brian Kernighan's n & (n-1) trick. LeetCode 338 extends that to an array using dynamic programming. Missing Number (LeetCode 268) uses XOR rather than bit counting, but all three problems reward fluency with bitwise operators and the core properties (commutativity, associativity, self-inverse) that make bit tricks work.

For a complete bit manipulation study path, work through Missing Number (268), Single Number (136), Number of 1 Bits (191), Counting Bits (338), Reverse Bits (190), and Sum of Two Integers (371) in that order. Each introduces a new core technique: XOR cancellation, popcount, DP recurrence, bit reversal, and bitwise addition with carry. Together they cover the full toolkit that appears in FAANG-level interviews under the bit manipulation category.