Skip to main content

268 - Missing Number

Difficulty: Easy | Pattern: Math / Bit Manipulation / Hash Set | Company tags: Amazon, Google, Microsoft

Problem Statement​

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3, 0, 1]
Output: 2
Explanation: n = 3, range is [0,1,2,3], 2 is missing.

Example 2:

Input: nums = [0, 1]
Output: 2

Example 3:

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

Constraints: n == nums.length; 1 <= n <= 10^4; all numbers are unique; range is [0, n]

Approach 1: Gauss Sum — O(n) time, O(1) space​

Key insight: The sum of numbers from 0 to n is n*(n+1)/2. The missing number equals this expected sum minus the actual sum.

def missingNumber(nums: list[int]) -> int:
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Example: nums = [3, 0, 1], n=3 Expected: 3*4/2 = 6 Actual sum: 3+0+1 = 4 Missing: 6 - 4 = 2 ✓

Algorithm Flow​

Approach 2: XOR Bit Manipulation — O(n) time, O(1) space​

Key insight: a XOR a = 0 and a XOR 0 = a. XOR all indices 0..n with all values. Each number that appears in both cancels out; only the missing number remains.

def missingNumber(nums: list[int]) -> int:
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

Why it works: For n=3 with [3, 0, 1]: result = 3 ^ (0^3) ^ (1^0) ^ (2^1) = 3^3^0^0^1^2^1 = 0^0^0^2 = 2

Approach 3: Hash Set — O(n) time, O(n) space​

def missingNumber(nums: list[int]) -> int:
    num_set = set(nums)
    for i in range(len(nums) + 1):
        if i not in num_set:
            return i

Approach 4: Sorting — O(n log n) time, O(1) space​

Sort and check where the index doesn't match the value.

Which to Use?​

ApproachTimeSpaceNotes
Gauss sumO(n)O(1)Risk of integer overflow in some languages (not Python)
XORO(n)O(1)No overflow risk; clever bit trick
Hash setO(n)O(n)Overkill for this problem
SortingO(n log n)O(1)Below the required time complexity

Recommended: Gauss sum (clean, readable) or XOR (demonstrates bit manipulation knowledge).

Key Terms​

TermDefinition
Gauss sum formulaClosed-form sum n*(n+1)/2 used to compute the expected total without looping twice
XOR cancellationProperty a ^ a = 0, a ^ 0 = a used to cancel matching index/value pairs, leaving the missing one
Hash set membershipO(1) average lookup structure used to check which value in [0, n] never appeared
In-place techniqueSolving with O(1) extra space by reusing arithmetic/bitwise identities instead of auxiliary structures

FAQ​

  1. Can this be solved without extra space? Yes — both the Gauss sum and XOR approaches use O(1) extra space; only the hash set approach uses O(n).
  2. What if the array is empty? Then n = 0 and the range is [0, 0], so the only possible missing number is 0, which both formulas handle correctly (expected sum is 0, XOR of nothing is 0).
  3. Does the Gauss sum approach risk overflow? In languages with fixed-width integers (e.g., Java, C++), n*(n+1) can overflow for large n; XOR avoids this entirely since it never computes a large intermediate sum.
  4. What's the follow-up interviewers usually ask? "What if two numbers are missing instead of one?" — this breaks the simple sum/XOR trick and typically requires a hash set or two-pass bit-splitting technique.
  5. How would this change if duplicates were allowed? The Gauss sum and XOR tricks rely on the range containing exactly n distinct values; with duplicates you'd need a hash set or sorting-based approach instead.

Quick Revision​

  • Range is [0, n] with n distinct values in an array of length n, so exactly one number is missing.
  • Gauss sum: missing = n*(n+1)/2 - sum(nums), O(n) time, O(1) space.
  • XOR: XOR all indices 0..n with all array values; matching pairs cancel, leaving the missing number.
  • Hash set: insert all values, then scan 0..n for the first absent one — O(n) space, easiest to explain.
  • Sorting approach is correct but exceeds the implied O(n) time bound.
  • Prefer XOR when overflow is a concern (non-Python languages); prefer Gauss sum for readability.
  • Edge case: single-element array [0] or [1] — both formulas still return the correct missing value.
  • Interviewers often push toward XOR to test bitwise fluency even when Gauss sum is simpler.
  • Single Number (LeetCode 136) — same XOR-cancellation pattern applied to duplicates instead of a missing value
  • First Missing Positive (LeetCode 41) — related "find missing value" family without the [0, n] guarantee
  • Two Missing Numbers (LeetCode 1060 / variant) — extends this pattern using bit-splitting when two numbers are missing