Set Mismatch
Asked at Microsoft
Problem
You are given a set of integers where one number is duplicated and one number is missing. Find both the duplicate and the missing number using O(n) time and O(1) space.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | EASY | View all Microsoft questions → |
How to Think About It
Brute force: sort the array and scan for the duplicate and missing numbers in a single pass.
Use a hash set to track seen numbers; the duplicate appears twice, and the missing number is absent.
Math approach: compute sum and sum of squares to derive the duplicate and missing via algebra.
Bit manipulation: XOR all elements with 1..n to isolate the duplicate and missing bits.
Optimal: use the sign-flipping technique by marking visited indices as negative to identify both numbers in one pass.
Optimal Approach
Compute the expected sum S = n(n+1)/2 and expected sum of squares Q = n(n+1)(2n+1)/6. The actual sum gives us (duplicate - missing) and the actual sum of squares gives (duplicate^2 - missing^2). Solving these two equations yields both values. Alternatively, iterate through the array and mark the index corresponding to each value by negating it; a repeated value means the index was already negated (duplicate), and the positive index at the end is the missing number.
What Trips People Up in Real Interviews
Clarify the range is 1..n and exactly one duplicate and one missing exist.
Do not confuse this with finding duplicates only — the missing number is equally important.
The bit manipulation XOR approach is elegant but tricky to explain under time pressure.
The sign-flipping in-place method is O(1) space but modifies the input array.
Confirm whether returning the pair [duplicate, missing] or separate variables.
Solution Code
def findErrorNums(nums):
n = len(nums)
xor_all = 0
for i in range(1, n + 1):
xor_all ^= i
for num in nums:
xor_all ^= num
diff_bit = xor_all & (-xor_all)
x = 0
y = 0
for i in range(1, n + 1):
if i & diff_bit:
x ^= i
else:
y ^= i
for num in nums:
if num & diff_bit:
x ^= num
else:
y ^= num
for num in nums:
if num == x:
return [x, y]
return [y, x]Frequently Asked Questions
What is the Set Mismatch problem?
You are given a set of integers where one number is duplicated and one number is missing. Find both the duplicate and the missing number using O(n) time and O(1) space.
How do you solve Set Mismatch?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Set Mismatch?
Set Mismatch is asked at Microsoft. It is a easy difficulty problem.
What are common mistakes on Set Mismatch?
- Clarify the range is 1..n and exactly one duplicate and one missing exist.
- Do not confuse this with finding duplicates only — the missing number is equally important.
- The bit manipulation XOR approach is elegant but tricky to explain under time pressure.
- The sign-flipping in-place method is O(1) space but modifies the input array.
- Confirm whether returning the pair [duplicate, missing] or separate variables.