Missing Number
Examples
Example 1:
Input: nums = [1,2,3]
Output: 0
Explanation:
Example 2:
Input: nums = [0,2]
Output: 1
Example 1:
Input: nums = [1,2,3]
Output: 0
Explanation:
Example 2:
Input: nums = [0,2]
Output: 1
Given an array nums containing n integers in the range [0, n] without any duplicates, return the single number in the range that is missing from nums.
Follow-up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
Since there are 3 numbers, the range is [0,3]. The missing number is 0 since it does not appear in nums.
1 <= nums.length <= 1000Use XOR. Initialize result with n, then XOR all indices and values. All paired numbers cancel out, leaving the missing number.
XORing a value with itself yields 0 and XOR is associative/commutative. The full set 0..n XORed with the array leaves only the missing element, since it is the only one not canceled.
O(n)O(1)class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
result = n
for i, num in enumerate(nums):
result ^= i ^ num
return result