Bit Manipulation XOR tricks
114. Set Mismatch
You are given an array nums of length n. It was meant to hold every integer from 1 to n exactly
once. But one of the values was overwritten with a copy of another value from the same range. Now one
value appears twice, and one value from 1 to n does not appear at all.
Return [duplicate, missing]: the value that appears twice, then the value that is missing.
The array can be in any order. Either value can be anywhere in the range, including 1 and n.
Example 1
Input: nums = [4, 1, 6, 2, 6, 3]
[6,5]Explanation: The range is 1 to 6. The value 6 appears twice, and 5 does not appear, so the answer is [6,5].
Example 2
Input: nums = [2, 3, 3]
[3,1]Explanation: The range is 1 to 3. The value 3 appears twice, and the missing value is 1, the start of the range.
Example 3
Input: nums = [1, 1]
[1,2]Explanation: The smallest array. The range is 1 to 2, so 1 is the duplicate and 2 is missing.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
n = nums.length2 ≤ n ≤ 1051 ≤ nums[i] ≤ n- Exactly one value appears twice, and every other value appears at most once.
Clarifying questions
What you would ask an interviewer before writing any code.