Missing Number

Problem

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.

Examples

The brute-force approach

For each number from 0 to n, check if it exists in nums using a linear scan or a Set.

seen = set(nums)
for i in range(len(nums) + 1):
    if i not in seen:
        return i

Building the set is O(n). The scan is O(n). Total O(n) time and O(n) space. This is acceptable, but there are O(n) time O(1) space solutions.

Spotting the pattern

This is a Bit Manipulation problem. The key question to ask yourself:

If you add up all numbers that should be there and subtract all numbers that are there, what's left?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.