Find Missing And Repeating numbers
Filed under MAQ Software · Also reported at Dolat Capital, Infoedge
Free read 1 of 3Input has exactly one duplicate and one missing value in range 1..n. Expected O(n) time and O(1) auxiliary space.
The question
Given an unsorted array of size n containing numbers from 1 to n, one number from the set {1, 2, ..., n} is missing and one number appears twice. Find and return both the repeating and missing numbers.
Constraints
- 2 <= n <= 10^5
- 1 <= arr[i] <= n
Examples
- Input
- arr = [3, 1, 3]
- Output
- [3, 2]
- Why
- 3 is repeated twice and 2 is missing from range [1, 3].
- Input
- arr = [4, 3, 6, 2, 1, 1]
- Output
- [1, 5]
- Why
- 1 is repeated and 5 is missing from range [1, 6].
Approach
Input has exactly one duplicate and one missing value in range 1..n. Expected O(n) time and O(1) auxiliary space.
Use array elements as 1-based indices. Negate `arr[abs(x) - 1]`. If already negative, x is the repeating number.
Iterate through the array again. The index with a positive value corresponds to the missing number.
Solution
O(n) time, O(1) auxiliary space
class Solution:
def findTwoElement(self, arr: list[int]) -> list[int]:
# returns [repeating, missing]
repeating = -1
missing = -1
for num in arr:
idx = abs(num) - 1
if arr[idx] < 0:
repeating = abs(num)
else:
arr[idx] = -arr[idx]
for i, val in enumerate(arr):
if val > 0:
missing = i + 1
break
return [repeating, missing]
Tips
- What they are testing: Tests mathematical manipulation or in-place array sign tagging for O(1) space constraints.
- Common mistake: Integer overflow when using sum and sum-of-squares formulas without 64-bit integers.
Related MAQ Software questions
Collected from public candidate posts and coding forums. Updated Nov 2026.