You are given an array with all the numbers from 1 to N appearing exactly once, except for two number that is missing. How can you find the missing number in O(N) time and 0(1) space?
You can return the missing numbers in any order.
Example 1:
Input: [1]
Output: [2,3]
Example 2:
Input: [2,3]
Output: [1,4]
Note:
nums.length <= 30000
class Solution:
def missingTwo(self, nums: List[int]) -> List[int]:
res, n = 0, len(nums)
for i in range(n):
res ^= nums[i]
res ^= (i + 1)
res ^= (n + 1)
res ^= (n + 2)
pos = 0
while (res & 1) == 0:
pos += 1
res >>= 1
a = b = 0
for num in nums:
t = num >> pos
if (t & 1) == 0:
a ^= num
else:
b ^= num
for i in range(1, n + 3):
t = i >> pos
if (t & 1) == 0:
a ^= i
else:
b ^= i
return [a, b]class Solution {
public int[] missingTwo(int[] nums) {
int res = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
res ^= nums[i];
res ^= (i + 1);
}
res ^= (n + 1);
res ^= (n + 2);
int pos = 0;
while ((res & 1) == 0) {
pos += 1;
res >>= 1;
}
int a = 0, b = 0;
for (int num : nums) {
int t = num >> pos;
if ((t & 1) == 0) {
a ^= num;
} else {
b ^= num;
}
}
for (int i = 1; i <= n + 2; ++i) {
int t = i >> pos;
if ((t & 1) == 0) {
a ^= i;
} else {
b ^= i;
}
}
return new int[]{a, b};
}
}