1. Set Mismatch (LeetCode)
Model answer
The task
An array contains values from 1 through its length, except one value appears twice and another is absent. Return the repeated value and the missing value, in that order.
Key idea
XOR all array values with all values in the expected range. Matching values cancel, leaving the XOR of the duplicate and missing values. Split the values by a distinguishing bit to recover both candidates, then count one candidate to determine which is repeated.
Approach
- XOR each array value and each expected value together.
- Find a set bit in the resulting XOR; the two answers differ at that bit.
- XOR values in each group separately to get the two candidates.
- Count one candidate in the array to identify the duplicate and return the result.
class Solution:
def findErrorNums(self, nums: list[int]) -> list[int]:
n = len(nums)
combined_xor = 0
# Equal values cancel, leaving duplicate XOR missing.
for expected, value in enumerate(nums, start=1):
combined_xor ^= expected ^ value
# The lowest set bit separates the two candidates.
distinguishing_bit = combined_xor & -combined_xor
candidate_a = 0
candidate_b = 0
for expected, value in enumerate(nums, start=1):
if value & distinguishing_bit:
candidate_a ^= value
else:
candidate_b ^= value
if expected & distinguishing_bit:
candidate_a ^= expected
else:
candidate_b ^= expected
# Exactly one candidate occurs twice in nums.
if sum(value == candidate_a for value in nums) == 2:
return [candidate_a, candidate_b]
return [candidate_b, candidate_a]
Complexity:
- Time: O(n), using a constant number of linear passes.
- Space: O(1), storing only a fixed number of variables.
Common follow-ups
- What if the input may contain more than one error? This XOR partition relies on exactly one duplicate and one missing value.
- Can you use a hash set? Yes; track seen values to find the duplicate, then scan
1..nfor the missing value, using O(n) extra space. - Can the input be modified? Sign marking can find both values in O(n) time and O(1) extra space, but it changes the array unless restored.