You are given a vector nums of n distinct numbers, each between 0 and n.
The range from 0 to n holds n + 1 numbers, so exactly one of them is not in nums. Return that missing number.
Example 1:
Input: nums = [3, 0, 1] Output: 2 Explanation: n = 3, so the numbers should be 0, 1, 2 and 3. 0, 1 and 3 are in nums: 2 is missing.
Example 2:
Input: nums = [0, 1] Output: 2 Explanation: n = 2, so the numbers should be 0, 1 and 2. The missing one can be n itself.
Example 3:
Input: nums = [1] Output: 0 Explanation: n = 1, so the numbers should be 0 and 1. The missing one can be 0.
Constraints:
n == nums.size()1 <= n <= 1050 <= nums[i] <= n- All the numbers in
numsare distinct.
Your algorithm should run in O(n) time and use O(1) extra space.
In Single Number, XOR made the pairs cancel:
x XOR x = 0, x XOR 0 = x, and the order doesn't matter. Here no number repeats. Can you give every number that is in nums a partner to cancel with?
The indices of
nums go from 0 to n - 1: add n and you have every number from 0 to n once. Start from n and XOR in every index and every value. Each value in nums meets its equal and cancels; the missing number has no partner among the values, so it is what is left.
We visit each index once, with two XORs per index: O(n) time.
We keep a single number, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
