Skip to main content
DSA patterns

Missing Number

easyArrays and hashing Must-doAmazonCiscoTCS Digital

Problem statement

You are given an array nums that holds n distinct numbers, all drawn from the range 0 to n inclusive. Since that range actually has n + 1 possible values but the array only holds n of them, exactly one value from the range never made it in. Find and return that missing value.

Think of it as a sanity check on a set of IDs — hosts numbered 0 through n, or ports allocated in sequence — where exactly one ID somehow never got issued, and you need to find which one.

Examples

Example 1

Input: nums = [3, 0, 1]

Output: 2

Explanation: There are 3 numbers in the array, so the full range is 0 to 3 (4 possible values). Of those, 0, 1, and 3 appear — 2 is the one that's missing.

Example 2

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output: 8

Explanation: There are 9 numbers, so the full range is 0 to 9 (10 possible values). Every value from 0 to 9 shows up except 8.

Hints

Hint 1: If nothing were missing, the array would hold every integer from 0 to n exactly once — that's a very specific, very checkable set.

Approach

Optimal: Sum formula

Intuition

Here's the shortcut: if nothing were missing, nums would hold every integer from 0 to n exactly once, and that specific set of numbers always adds up to the same fixed total — n(n+1)/2 (Gauss's classic formula). Since exactly one value is missing, the array's actual sum falls short of that expected total by precisely the missing value. Subtract one from the other and you have your answer directly, no searching required.

Steps

  1. Let n be the length of nums.
  2. Compute the expected sum of 0 through n: n * (n + 1) / 2.
  3. Compute the actual sum of every value in nums.
  4. Return expected sum − actual sum.

Dry run

nums = [3, 0, 1], n = 3.

quantity value
expected sum (0+1+2+3) 6
actual sum (3+0+1) 4
missing = expected − actual 6 − 4 = 2

For nums = [9, 6, 4, 2, 3, 5, 7, 0, 1], n = 9: expected sum is 9·10/2 = 45, actual sum is 9+6+4+2+3+5+7+0+1 = 37, so the missing value is 45 − 37 = 8.

Edge case: nums = [] gives n = 0, expected sum 0, actual sum 0, so the answer is 0 — correct, since the only value in the range [0, 0] is 0 itself, and it's missing.

Complexity

Time O(n) - a single pass over `nums` to total it up, plus one O(1) formula calculation. No set, no repeated scanning.

Space O(1) - only two numbers are ever tracked (the expected sum and the actual sum), regardless of how large `nums` is.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum


if __name__ == "__main__":
    print(Solution().missingNumber([3, 0, 1]))  # 2
    print(Solution().missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # 8
RecapThe whole problem in a few lines, for the night before
  • Spot it: an array of n distinct values drawn from the range [0, n] with exactly one value left out
  • Idea: the numbers 0..n always sum to n(n+1)/2 — subtract the array's actual sum from that to isolate the missing value directly (XOR of indices and values works the same way, without overflow risk)
  • Cost: O(n) time, O(1) space (hash-set version: O(n) time, O(n) space)
  • Trap: forgetting the range has n+1 possible values while the array only holds n — off-by-one errors here are the most common mistake

Interview follow-ups

  • The problem's own follow-up asks for O(1) extra space and O(n) time — which approach satisfies that?

    Both the sum-formula approach and the XOR approach meet this: each does one pass over the array (O(n) time) and tracks only a couple of numbers along the way (O(1) space), unlike the hash-set approach which needs O(n) space to hold the set.

  • What if the array could contain duplicates, and you still needed to find a missing value from the range?

    The sum-formula trick breaks immediately, since duplicates throw off the actual sum without telling you which specific value is missing versus over-counted. You'd need to go back to a presence check — a hash set of size up to n, or, since the range is bounded, a boolean array of size n + 1 marking which values were seen — then scan for the first unmarked slot.

Frequently asked questions

Gauss's formula says the numbers 0 through n always sum to n(n+1)/2, a fact you can derive by pairing the smallest and largest remaining numbers (0+n, 1+(n-1), 2+(n-2)...) which each add up to n. Because exactly one value is missing from an otherwise complete set, subtracting the array's real sum from that fixed expected total isolates exactly the missing number. On overflow: with LeetCode's constraint of n up to 10,000, the largest possible sum is about 50 million, which fits comfortably in a standard 32-bit int in Java and C++ — but for much larger n you'd want to switch to a 64-bit type or compute the difference incrementally to stay safe.

XOR every index 0 through n together with every value in nums. Since x XOR x = 0, every value that appears in both the index range and the array cancels itself out, leaving only the one unmatched value — the missing number. It's the same O(n) time and O(1) space as the sum approach, and it completely sidesteps the overflow question since XOR never grows a running total the way addition does. Either is a fine "optimal" answer in an interview; mentioning both shows you know more than one trick for this shape of problem.

Finding a gap in an expected sequence is a real operational question: which instance ID, port number, or sequential log entry never showed up. The sum-formula trick specifically shows whether a candidate knows a classic technique for "detect the one missing item from a known, complete range" rather than reaching straight for a heavier data structure.

Yes — the constraints say nums holds n distinct values, each between 0 and n inclusive, which is a range of n + 1 possible values. Since only n of those n + 1 slots are filled and every value present is unique, precisely one value from the range is left out. If duplicates were allowed, or more than one value could be missing, none of the three approaches here would work as written.