The Gap in the Sequence

Difficulty: Medium · Pattern: Cyclic Sort / Array Math · Concept: General Coding (DSA) — Core Patterns to Drill

You're given a list of n distinct integers, each drawn from the range 0 to n inclusive (that's n + 1 possible values), with exactly one value missing. Find the missing one.

The cyclic sort family of problems exploits a strong constraint most array problems don't have: when values are known to fall in a bounded, contiguous range tied to the array's own length, you can reason about "where should this value be" instead of searching or sorting generally. Here that constraint gives an even more direct route: a closed-form sum.

Your task: implement find_missing_number(nums) in $O(n)$ time and $O(1)$ extra space (no set, no counting array).

Next: Find All Duplicates in an Array (a harder variant), or continue to Largest Rectangle in a Skyline