268. Missing Number (Easy)

Problem

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

Example

nums = [3, 0, 1] → 2
nums = [0, 1] → 2
nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8

LeetCode 268 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Hash set

Put everything into a set, then scan [0, n] for the missing value.

def missing_number(nums):
    s = set(nums)                           # L1: O(n)
    for i in range(len(nums) + 1):          # L2: scan 0..n
        if i not in s:                      # L3: O(1) amortized
            return i
    return -1

function missingNumber(nums: number[]): number {
    const s = new Set(nums);                // L1: O(n)
    for (let i = 0; i <= nums.length; i++) { // L2: scan 0..n
        if (!s.has(i)) return i;            // L3: O(1) amortized
    }
    return -1;
}

func missingNumber(nums []int) int {
    s := make(map[int]bool)                 // L1: O(n)
    for _, x := range nums {
        s[x] = true
    }
    for i := 0; i <= len(nums); i++ {       // L2: scan 0..n
        if !s[i] {                          // L3: O(1) amortized
            return i
        }
    }
    return -1
}

final class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        var candidates = Set(0...nums.count)
        for value in nums {
            candidates.remove(value)
        }
        return candidates.first ?? 0
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (build set)	$O(1)$	n	$O(n)$ ← dominates
L2-L3 (scan)	$O(1)$	n+1	$O(n)$

Complexity

Time: $O(n)$ , driven by L1/L2/L3 (one pass to build set, one to scan).
Space: $O(n)$ for the set.

Approach 2: Sum formula

Expected sum of [0, n] is n(n + 1)/2. Missing = expected - actual.

def missing_number(nums):
    n = len(nums)                           # L1: O(1)
    return n * (n + 1) // 2 - sum(nums)    # L2: O(n)

function missingNumber(nums: number[]): number {
    const n = nums.length;                              // L1: O(1)
    return n * (n + 1) / 2 - nums.reduce((a, b) => a + b, 0); // L2: O(n)
}

func missingNumber(nums []int) int {
    n := len(nums)                          // L1: O(1)
    expected := n * (n + 1) / 2            // L2: O(1), Gauss formula
    actual := 0
    for _, x := range nums {               // L3: O(n), sum all elements
        actual += x
    }
    return expected - actual               // L4: O(1)
}

final class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        let count = nums.count
        let expected = count * (count + 1) / 2
        return expected - nums.reduce(0, +)
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (get length)	$O(1)$	1	$O(1)$
L2 (sum)	$O(n)$	1	$O(n)$ ← dominates

Complexity

Time: $O(n)$ , driven by L2 (summing all elements).
Space: $O(1)$ .

Risk of overflow in fixed-width languages for large n (not an issue in Python or JavaScript’s 64-bit floats for this constraint).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: XOR of indices and values (optimal, overflow-safe)

XOR all values 0…n with all array elements. Pairs cancel; missing remains.

def missing_number(nums):
    result = len(nums)                      # L1: O(1), start with n
    for i, x in enumerate(nums):            # L2: single pass, n iterations
        result ^= i ^ x                     # L3: O(1), cancel paired values
    return result

function missingNumber(nums: number[]): number {
    let result = nums.length;               // L1: O(1), start with n
    for (let i = 0; i < nums.length; i++) { // L2: single pass, n iterations
        result ^= i ^ nums[i];              // L3: O(1), cancel paired values
    }
    return result;
}

func missingNumber(nums []int) int {
    result := len(nums)                     // L1: O(1), start with n
    for i, x := range nums {               // L2: single pass, n iterations
        result ^= i ^ x                    // L3: O(1), cancel paired values
    }
    return result
}

final class Solution {
    func missingNumber(_ nums: [Int]) -> Int {
        var result = nums.count
        for (index, value) in nums.enumerated() {
            result ^= index ^ value
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init with n)	$O(1)$	1	$O(1)$
L2, L3 (XOR loop)	$O(1)$	n	$O(n)$ ← dominates

A single pass; each element and index are XORed in once.

Complexity

Time: $O(n)$ , driven by L2/L3 (single XOR pass).
Space: $O(1)$ .

Why it works

Result starts at n. We XOR in every index 0..n-1 and every value from nums. Every number from 0..n except the missing one appears exactly twice (once as an index, once as a value); each cancels to 0. The initial n and the missing value survive, but n is also present as an index of the initial XOR, so it cancels unless it’s the missing one… Actually here’s the clean reading: we start with n, then XOR in all i and all nums[i]; the set {0..n} ∪ {all nums} has every value except the missing appearing an even number of times. Net result = missing.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

The Set approach allocates candidates from 0...n. The sum and XOR approaches keep constant auxiliary state. Swift arrays use value semantics, so these implementations do not mutate the caller’s array. The published limit keeps the arithmetic-series total safely inside Int on the supported runner.

Summary

Approach	Time	Space	Notes
Hash set	$O(n)$	$O(n)$	Straightforward
Sum formula	$O(n)$	$O(1)$	Overflow-sensitive
XOR	$O(n)$	$O(1)$	Overflow-safe

Test cases

# Quick smoke tests, paste into a REPL or save as test_268.py and run.
# Uses the canonical implementation (Approach 3: XOR).

def missing_number(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result

def _run_tests():
    assert missing_number([3, 0, 1]) == 2
    assert missing_number([0, 1]) == 2
    assert missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
    assert missing_number([0]) == 1         # missing 1
    assert missing_number([1]) == 0         # missing 0, edge case
    assert missing_number([0, 1, 2, 4, 5]) == 3  # missing middle
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function missingNumber(nums: number[]): number {
    let result = nums.length;
    for (let i = 0; i < nums.length; i++) result ^= i ^ nums[i];
    return result;
}

console.assert(missingNumber([3, 0, 1]) === 2);
console.assert(missingNumber([0, 1]) === 2);
console.assert(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]) === 8);
console.assert(missingNumber([0]) === 1);
console.assert(missingNumber([1]) === 0);
console.assert(missingNumber([0, 1, 2, 4, 5]) === 3);
console.log("all tests pass");

func missingNumber(nums []int) int {
    result := len(nums)
    for i, x := range nums {
        result ^= i ^ x
    }
    return result
}

None; pure arithmetic.

Bit Manipulation, the binary representation pattern for masks, toggles, shifts, and arithmetic shortcuts.
Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.

268. Missing Number (Easy)

Problem

Try it yourself

Approach 1: Hash set

Approach 2: Sum formula

Approach 3: XOR of indices and values (optimal, overflow-safe)

Why it works

Swift notes

Summary

Test cases

Related data structures

Related concepts