Find the repeating and missing number
Google
J.P. MorganThe problem
Given an integer array **nums **of size n containing values from [1, n] and **each **value appears **exactly **once in the array, except for A, which appears **twice **and B which is missing.
Return the values A and B, as an array of size 2, where A appears in the 0-th index and **B **in the 1st index.
**Note: **You are not allowed to modify the original array.
Input: nums = [3, 5, 4, 1, 1] Output: [1, 2] Explanation: 1 appears two times in the array and 2 is missing from nums
Input: nums = [1, 2, 3, 6, 7, 5, 7] Output: [7, 4] Explanation: 7 appears two times in the array and 4 is missing from nums.
Input: nums = [6, 5, 7, 1, 8, 6, 4, 3, 2]
- n == nums.length
- 1 <= n <= 105
- n - 2 elements in nums appear exactly once and are valued between [1, n].
- 1 element in nums appears twice, and is valued between [1, n].
cpp
class Solution {
public:
vector<int> findMissingRepeatingNumbers(vector<int> nums) {
}
};java
class Solution {
public int[] findMissingRepeatingNumbers(int[] nums) {
}
}python
class Solution:
def findMissingRepeatingNumbers(self, nums):javascript
class Solution {
findMissingRepeatingNumbers(nums) {
}
}csharp
public class Solution {
public List<int> FindMissingRepeatingNumbers(List<int> nums) {
}
}go
func findMissingRepeatingNumbers(nums []int) []int {
}Stuck? Show a way to structure it+
- 01Compute expected and observed sums and squared sums, or use XOR partitioning.
- 02Derive duplicate-minus-missing from the sum difference.
- 03Solve for both values and preserve output order.
- 04Use wide numeric types for arithmetic.
Reference answer
Then expect these follow-ups
Explain the XOR partition solution.
Tests: bit manipulation
What changes with multiple duplicates and missing values?
Tests: problem limits
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question