Description
An array contains n distinct values drawn from 0 through n. Return the missing value.
Solution
def missing_number(nums):
missing = len(nums)
for i,value in enumerate(nums):
missing ^= i ^ value
return missingExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[0,2]]- Output
1
1 is absent from the range 0 through 2.
Example 2
- Input
[[1]]- Output
0
The range is 0 through 1 and zero is absent.
Example 3
- Input
[[0,1]]- Output
2
The missing value is the upper endpoint.
Approach
XOR all indices, all values, and n; paired values cancel.
Time & space
O(n) time; O(1) space. Here n is the input length.