Missing Number
Easy · Bit Manipulation · Array · Math · Bit Manipulation
Problem
nums holds n distinct values drawn from the range 0 to n. Exactly one value in that range is absent — return it.
Aim for O(n) time and O(1) extra space.
Examples
Input: nums = [3,0,1] Output: 2
n = 3, and 2 is missing from 0..3.
Input: nums = [0,1] Output: 2
n = 2, and 2 is missing.
Constraints
- n == len(nums)
- 1 <= n <= 10^4
- All values are distinct and within 0..n
Approaches
- Gauss sum — time O(n), space O(1)
Follow-up
Can you solve it using only O(1) extra space and O(n) time?
Related problems
Start free on Cariara · Coding problems · System design studio
