645. Set Mismatch
Asked at Microsoft
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are given an array nums that should contain every integer from 1 to n exactly once, where n is the length of the array. But one value got copied over another value, so now one number appears twice and one number is missing.
Return a two-element array [duplicate, missing]. The first element is the number that shows up twice, and the second is the number that never shows up.
You may assume the array always has exactly one duplicate and exactly one missing value, so there is always a single correct answer.
One value copied, one value lost
Constraints
- ●
2 <= nums.length <= 10^4 - ●
1 <= nums[i] <= 10^4
Examples
nums = [1,2,2,4][2,3]nums = [1,1][1,2]Asked At
1 companies| 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.
XOR everything, then split by one bit
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.