← MAQ Software questions

Find Missing And Repeating numbers

Filed under MAQ Software · Also reported at Dolat Capital, Infoedge

Free read 1 of 3

Input 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

  1. Input has exactly one duplicate and one missing value in range 1..n. Expected O(n) time and O(1) auxiliary space.

Solution

O(n) time, O(1) auxiliary space

Python
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.