Find Corrupt Pair
Easy · Arrays & Hashing · Array · Hash Table · Sorting · Cyclic Sort
Problem
An array nums of length n was supposed to hold every integer from 1 to n exactly once. Because of a data error, one number was overwritten with a copy of another, so one value now appears twice and one value is missing.
Return [duplicate, missing]: the value that appears twice, then the value that no longer appears.
Try for O(n) time and O(1) extra space. A cyclic-sort pass that puts each value v at index v - 1 leaves exactly one index i holding the wrong value: that value is the duplicate, and i + 1 is the missing number.
Examples
Input: nums = [3,1,3,4] Output: [3,2]
3 appears twice and 2 does not appear.
Input: nums = [2,2] Output: [2,1]
2 appears twice, so 1 is the missing value.
Input: nums = [1,5,3,2,2] Output: [2,4]
2 appears twice and 4 never appears.
Constraints
- 2 <= n <= 10^4
- len(nums) == n
- 1 <= nums[i] <= n
- Exactly one value appears twice and exactly one value is missing
Approaches
- Count each value — time O(n), space O(n)
Follow-up
Without modifying the array and in O(1) space, two equations recover both values: the sum of nums differs from n(n + 1) / 2 by duplicate - missing, and the sum of squares differs by duplicate² - missing²; dividing gives duplicate + missing. XOR-ing all values with 1..n gives duplicate ^ missing, and splitting by its lowest set bit separates them.
Related problems
Start free on Cariara · Coding problems · System design studio
