Cyclic Sort
LC #268Easy
Missing Number
Cyclic Sort
AmazonGoogleMicrosoftAppleProblem
Given an array nums of n distinct numbers in the range [0, n], find and return the one number that is missing. Example: [3,0,1] → 2 (range is 0–3, the number 2 is absent). Two approaches: Gauss formula (sum trick) or XOR — both O(1) space.
arraymathbit-manipulation
Constraints
- ›n == nums.length
- ›1 ≤ n ≤ 10⁴
- ›0 ≤ nums[i] ≤ n
- ›All numbers are unique
- ›O(1) extra space preferred
Example
Input
nums = [3, 0, 1]Output
2Why
n = 3, range [0,3]. All present except 2