Missing Number LeetCode Solution — Complete Walkthrough

Missing Number (#268) is one of the most deceptively instructive Easy problems on LeetCode. The problem itself is straightforward — find the one number missing from a sequence — but what makes it shine in interviews is the variety of valid approaches you can present. Interviewers are not just testing whether you can solve it. They want to see you reason about trade-offs.

Three distinct approaches solve this problem optimally: the Gauss sum formula, XOR bit manipulation, and a hash set lookup. Each runs in O(n) time, but they differ in space complexity, overflow risk, and elegance. Being able to walk through all three and explain why you prefer one over the others is exactly what separates a good interview performance from a great one.

If you are preparing for coding interviews at any level, this missing number leetcode problem is a must-practice. It bridges math, bit manipulation, and hashing — three of the most fundamental tools in your algorithm toolkit.

You are given an array nums containing n distinct numbers taken from the range [0, n]. Since the range has n+1 numbers but the array only has n elements, exactly one number is missing. Your job is to find and return it.

For example, given nums = [3, 0, 1], the range is [0, 3] and the missing number is 2. Given nums = [9, 6, 4, 2, 3, 5, 7, 0, 1], the range is [0, 9] and the missing number is 8. The array is not sorted, and the values can appear in any order.

The brute-force approach would sort the array and scan for the gap, but that costs O(n log n) time. Every optimal approach runs in O(n) time — the question is how much extra space you use and whether you risk integer overflow.

The mathematical approach uses a formula attributed to Carl Friedrich Gauss: the sum of all integers from 0 to n is n*(n+1)/2. If you compute this expected sum and subtract the actual sum of the array, the difference is the missing number. It is elegant, runs in O(n) time, and uses O(1) extra space.

For nums = [3, 0, 1], n = 3. The expected sum is 3*4/2 = 6. The actual sum is 3+0+1 = 4. The missing number is 6 - 4 = 2. Simple and fast.

However, the gauss formula missing number approach has a subtle risk. For very large values of n, the expected sum n*(n+1)/2 can overflow in languages with fixed-size integers like Java or C++. In Python this is not a concern because integers have arbitrary precision, but in a Java interview you should mention this limitation. The actual sum can also be large, so even the subtraction does not fully protect you.

The XOR approach is the cleanest solution and the one most interviewers consider the gold standard for this problem. The key property of XOR is that a ^ a = 0 and a ^ 0 = a. If you XOR all the numbers in the array with all the numbers from 0 to n, every number that appears in both sets cancels out, leaving only the missing number.

Start with a variable result = 0. XOR it with every index from 0 to n, and XOR it with every element in the array. Since every number except the missing one appears exactly twice across the combined set — once as an index and once as an array value — they all cancel. The missing number appears only once (as an index) and survives.

This XOR missing number approach runs in O(n) time and O(1) space, just like the math approach. But it has a critical advantage: no overflow risk. XOR operates on individual bits and never produces a value larger than the largest input. In languages with fixed-size integers, this makes XOR strictly superior to the sum formula.

For nums = [3, 0, 1], you compute 0^0^1^2^3 ^ 3^0^1 = 2. The pairs (0,0), (1,1), (3,3) cancel to zero, and 2 remains.

The hash set approach is the most intuitive. Insert every number from the array into a set. Then iterate from 0 to n and check which number is not in the set. The first number missing from the set is your answer.

This runs in O(n) time for both building the set and scanning the range. However, it uses O(n) extra space to store the set. In an interview, this is the approach you might code first as a "brute force" before optimizing to XOR or the sum formula.

The hash set method has no overflow risk and is easy to understand, which makes it a good starting point in a conversation. But when the interviewer asks you to optimize space, you pivot to XOR or math. Presenting the hash set first and then improving shows clear problem-solving progression — exactly what interviewers want to see.

Missing Number has several edge cases that are easy to overlook if you only test with the standard examples. Make sure your solution handles all of them before submitting.

When the missing number is 0, the array contains every number from 1 to n. Your algorithm must not assume the missing value is always in the interior of the range. When the missing number is n — the largest possible value — the array contains 0 through n-1. Both XOR and the sum formula handle these cases naturally without any special logic.

For single-element arrays, nums = [0] means the missing number is 1, and nums = [1] means the missing number is 0. These are minimal but valid inputs. If your loop bounds or XOR initialization are off by one, these cases will catch the bug immediately.

Missing Number is a small problem with a big lesson: the same problem can have multiple optimal solutions with different trade-offs. The Gauss formula is fast and space-efficient but risks overflow. The hash set is simple but wastes space. XOR is the sweet spot — no overflow, no extra space, and a clean implementation. Knowing all three and articulating the trade-offs is what makes this problem an interview favorite.

The XOR technique generalizes to other missing number bit manipulation problems. Single Number (#136) uses the same property to find the one non-duplicate in an array. Single Number II (#137) and Single Number III (#260) extend the idea further. If XOR feels unfamiliar, practicing these problems will make the pattern second nature.

If you want to lock this pattern into long-term memory, review Missing Number and the broader bit manipulation family with YeetCode flashcards. The difference between recognizing XOR as the right tool instantly and struggling to recall it under pressure is spaced repetition — and that is exactly what YeetCode is built for.