Missing number

Baseline Arrays · Easy O(n) · O(1)

The Badge That Never Checked In

An access-control system issues badges numbered 0 through n, and an end-of-day audit dumps every badge that badged in exactly once. Exactly one badge is missing from the dump. Identify it without sorting the attendance log.

Input: An array nums of n distinct integers drawn from the range [0, n].

Output: The single integer in [0, n] that does not appear in nums.

Constraints

1 <= n <= 10^4
0 <= nums[i] <= n
All values in nums are distinct

Examples

Example 1

Input: {"nums":[3,0,1]}
Output: 2
The badges 0,1,3 checked in, so the untouched badge in [0,3] is 2.

Example 2

Input: {"nums":[0,1]}
Output: 2
With two entries present, the range is [0,2] and the absent badge is the upper bound itself.

Solve this in your browser →

Also on LeetCode ↗