An array contains all the integers from 0 to n, except for one number which is missing. Write code to find the missing integer. Can you do it in O(n) time?
Note: This problem is slightly different from the original one the book.
Example 1:
Input: [3,0,1] Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1] Output: 8
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = 0
for i, num in enumerate(nums):
res ^= i
res ^= num
res ^= len(nums)
return resclass Solution {
public int missingNumber(int[] nums) {
int res = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
res ^= i;
res ^= nums[i];
}
res ^= n;
return res;
}
}