Missing Number
An array holds n distinct numbers from the range 0 to n, so exactly one is missing; find it. Tests whether you can use a sum or XOR identity instead of sorting or a set. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an array nums of n distinct integers, each between 0 and n inclusive. That range has n + 1 values, so exactly one of them is not in the array.
Return the missing value. The array is in no particular order.
Example 1
- Input
- nums = [4, 0, 1, 3]
- Output
- 2
n = 4, so the range is 0 to 4. Every value except 2 is present.
Example 2
- Input
- nums = [1, 2]
- Output
- 0
The range is 0 to 2, and 0 is the one that is absent.
Example 3
- Input
- nums = [0, 1, 2, 3, 4]
- Output
- 5
The missing value can be n itself.
Constraints
- 1 ≤ n = nums.length ≤ 10⁴
- 0 ≤ nums[i] ≤ n
- All values in nums are distinct.
Practice
Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Missing Number in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Missing Number
Pattern: Sum or XOR identity
You know exactly which values should be there: 0, 1, ..., n. If you can summarize the full range and the actual array in a way where every present number cancels out, whatever is left over is the missing one.
Two summaries do that:
- Sum. The full range adds up to
n(n + 1) / 2. Subtract the array's sum and the difference is the missing value. - XOR.
x ^ x = 0, so XOR every index0..ntogether with every value. Each present number appears twice and cancels, leaving only the missing one.
Both are one pass with constant extra memory.
Approach 1: Sort and scan
Sort the array, then find the first index i where nums[i] != i. If there is none, the answer is n. Easy to reason about, but sorting costs O(n log n) and either modifies the input or copies it.
Time O(n log n) · Space O(1) to O(n)
Approach 2: Hash set
Put every value in a set, then check 0..n and return the first value that is not in it. Linear time, but O(n) extra memory for something that only needs one number.
Time O(n) · Space O(n)
Approach 3: Expected sum minus actual sum
Compute n * (n + 1) / 2, the sum of the full range, and subtract every element of nums from it. What remains is the missing value.
The XOR version is equivalent: start with n, then XOR in each index i and each nums[i]. It avoids large intermediate sums, which matters in languages with fixed-width integers.
Time O(n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Sort and scan | O(n log n) | O(1) to O(n) |
| Hash set | O(n) | O(n) |
| Expected sum minus actual sum | O(n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Missing Number solution in Python
def missing_number(nums: list[int]) -> int:
n = len(nums)
missing = n * (n + 1) // 2 # sum of 0..n
for num in nums:
missing -= num
return missingMissing Number solution in JavaScript
function missingNumber(nums) {
const n = nums.length;
let missing = (n * (n + 1)) / 2; // sum of 0..n
for (const num of nums) missing -= num;
return missing;
}Common mistakes
- Using `nums.length - 1` as n. The array has n elements and the range is 0 to n, so n is the length itself.
- Forgetting that the missing value can be 0 or n, the two ends of the range.
- In the sort-and-scan version, not returning n when every index matches.
- Integer overflow on the sum in fixed-width languages. Subtracting as you go, or using XOR, avoids it.
What interviewers look for
Mention the set and sort answers briefly, then say the key observation: "I know exactly which numbers should be present, so I can compare a summary of what should be there against what is there." Interviewers like hearing you name the overflow concern with the sum formula and offer XOR as the fix, even in Python where it doesn't apply.
Test both boundary answers, 0 and n, before you finish.
Follow-up questions
What if two numbers were missing from 0..n+1?
The sum gives a + b and the sum of squares gives a² + b², which is enough to solve for both. With XOR, the total gives a ^ b; pick any set bit of it, split all numbers by that bit, and XOR each half separately to get a and b.
What if the array is sorted?
Binary search for the first index where nums[i] != i. Every index before it matches and every index after it is off by one, so the condition is monotonic. That is O(log n).
What if values could repeat and you had to find the first missing positive?
That is a different problem. The usual answer places each value v in slot v - 1 by swapping in place (cyclic sort), then scans for the first slot that does not hold its own value. O(n) time, O(1) extra space.
Companies that ask Missing Number
Missing Number is tagged by 85 companies in our interview dataset. The score shows how often it comes up at each company.
- Coffee Meets Bagel100%
- GE Aerospace100%
- Lonza100%
- Elevance Health93%
- Carbon Health93%
- Byjus89%
- Atos86%
- Intercom85%
- Lendingclub85%
- Amperity81%
- Alation81%
- Appier79%
- Arista Networks78.3%
- Merck77%
- Hackerrank76%
- Chegg75%
- Biontech74%
- Nerdwallet73%
- 6sense72%
- Sigma Computing72%
- Darktrace70%
- Wolters Kluwer69%
- F5 Networks68%
- Arcutis Biotherapeutics68%
and 61 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required