Missing Number (XOR)

Medium~15 min

Given an array nums containing n distinct numbers in the range [0, n], return the one number in the range that is missing from the array.

Use XOR bit manipulation to solve this in O(n) time and O(1) extra space.

For example, given nums = [3, 0, 1], the range is [0, 3] and the missing number is 2.

Examples

Example 1
Input: nums = [3, 0, 1]
Output: 2
Explanation: Range is [0, 3]. The numbers 0, 1, 3 are present. 2 is missing.
Example 2
Input: nums = [0, 1]
Output: 2
Explanation: Range is [0, 2]. The numbers 0, 1 are present. 2 is missing.
Example 3
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation: Range is [0, 9]. 8 is the only missing number.

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All values in nums are distinct
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run