Missing And Repeating – GeeksforGeeks Solution Explained

If you’re preparing for coding interviews, the “Missing And Repeating” problem is a classic! In this blog, we’ll explain the problem, walk you through brute force, better, and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Given an unsorted array arr of positive integers. One number a from the set [1, 2,….,n] is missing and one number b occurs twice in the array. Find numbers a and b.

Note: The test cases are generated such that there always exists one missing and one repeating number within the range [1,n].

Here’s the [Problem Link] to begin with.

Examples:

Input: arr[] = [2, 2]
Output: [2, 1]
Explanation: Repeating number is 2 and smallest positive missing number is 1.

Input: arr[] = [1, 3, 3] 
Output: [3, 2]
Explanation: Repeating number is 3 and smallest positive missing number is 2.

Input: arr[] = [4, 3, 6, 2, 1, 1]
Output: [1, 5]
Explanation: Repeating number is 1 and the missing number is 5.

Constraints:
2 ≤ arr.size() ≤ 10⁶
1 ≤ arr[i] ≤ arr.size()

Brute Force Solution (Nested Loops)

Intuition and Approach

Let’s solve the problem in the simplest way:

1. Count Occurrences:
   For each number from 1 to n, count how many times it appears in the array.
2. Identify Repeating and Missing:
   • If a number appears twice, it’s the repeating number.
   • If a number doesn’t appear at all, it’s the missing number.
3. Why does this work?
   We check every number, so we’re sure to find both the missing and repeating numbers.

This approach is easy to understand but not efficient for large arrays.

Code Implementation

class Solution:
    def findTwoElement(self, arr):
        n = len(arr)
        repeating, missing = -1, -1

        for i in range(1, n + 1):
            count = 0
            for j in range(n):
                if arr[j] == i:
                    count += 1

            if count == 2:
                repeating = i
            elif count == 0:
                missing = i

            if repeating != -1 and missing != -1:
                break

        return [repeating, missing]

Code Explanation

• For each number from 1 to n, we count how many times it appears in the array.
• If a number appears twice, we store it as repeating.
• If a number doesn’t appear at all, we store it as missing.
• As soon as we find both, we return the answer.

Dry Run

Input:
arr = [1][1]

• Check 1: appears 2 times → repeating = 1
• Check 2: appears 1 time
• Check 3: appears 1 time
• Check 4: appears 1 time
• Check 5: appears 0 times → missing = 5
• Check 6: appears 1 time

Output:
[1]

Time and Space Complexity

• Time Complexity: O(n^2)
  Two nested loops: for each number, check the whole array.
• Space Complexity: O(1)
  Only a few variables are used.

Conclusion

The brute force approach is simple and good for understanding, but it’s too slow for large arrays.

Better Solution (Hashing)

Intuition and Approach

Let’s make it faster using extra space:

1. Create a Hash Array:
   Make an array to count how many times each number appears.
2. Scan for Repeating and Missing:
   • If a number appears twice, it’s the repeating number.
   • If a number doesn’t appear, it’s the missing number.
3. Why does this work?
   Counting with a hash array is much faster than nested loops.

Code Implementation

class Solution:
    def findTwoElement(self, arr):
        n = len(arr)
        repeating, missing = -1, -1

        hash_list = [0] * (n + 1)              # create a hash list to count occurrences
        for num in arr:
            hash_list[num] += 1                # count each number

        for i in range(1, len(hash_list)):
            if hash_list[i] == 2:              # found repeating number
                repeating = i
            elif hash_list[i] == 0:            # found missing number
                missing = i
            if repeating != -1 and missing != -1:
                return [repeating, missing]

Code Explanation

• We use a hash array to count how many times each number appears.
• If a number appears twice, it’s repeating.
• If a number doesn’t appear, it’s missing.
• As soon as we find both, we return the answer.

Dry Run

Input:
arr = [1][1]

• hash_list after counting: [1][1][1][1]
• 1 appears 2 times → repeating = 1
• 5 appears 0 times → missing = 5

Output:
[1]

Time and Space Complexity

• Time Complexity: O(n)
  One pass to count, one pass to check.
• Space Complexity: O(n)
  Extra space for the hash array.

Conclusion

The better solution is much faster and is a good choice for medium-sized arrays.

Optimal Solution (Maths: Sum and Sum of Squares)

Intuition and Approach

Let’s solve the problem with no extra space and in just one pass:

1. Maths Approach:
   • Let the missing number be y and the repeating number be x.
   • Calculate the sum and sum of squares of the first n natural numbers.
   • Calculate the sum and sum of squares of the array.
   • Use these two equations:
     • x - y = sum(arr) - sum(1...n)
     • x^2 - y^2 = sum_of_squares(arr) - sum_of_squares(1...n)
2. Solve the Equations:
   • From above, calculate x + y and then find x and y.
3. Why does this work?
   The difference in sums and squares gives us two equations to solve for the missing and repeating numbers.

Code Implementation

class Solution:
    def findTwoElement(self, arr):
        n = len(arr)
        sN = (n * (n + 1)) // 2                      # sum of first n numbers
        s2N = (n * (n + 1) * (2 * n + 1)) // 6       # sum of squares of first n numbers

        s = 0
        s2 = 0
        for num in arr:
            s += num                                 # sum of array
            s2 += num**2                             # sum of squares of array

        val1 = s - sN                                # x - y
        val2 = s2 - s2N                              # x^2 - y^2

        val2 = val2 // val1                          # (x^2 - y^2) // (x - y) = x + y
        x = (val1 + val2) // 2                       # repeating number
        y = x - val1                                 # missing number

        return [x, y]

Code Explanation

• Calculate expected sum and sum of squares for numbers 1 to n.
• Calculate actual sum and sum of squares for the given array.
• Use the differences to set up equations and solve for missing and repeating numbers.

Dry Run

Input:
arr = [1][1]

• n = 6
• sN = 21, s2N = 91
• s = 17, s2 = 63
• val1 = s – sN = -4
• val2 = s2 – s2N = -28
• val2 // val1 = 7
• x = (val1 + val2) // 2 = (–4 + 7) // 2 = 1
• y = x – val1 = 1 – (–4) = 5

Output:
[1]

Time and Space Complexity

• Time Complexity: O(n)
  Only one pass for sums.
• Space Complexity: O(1)
  Only variables, no extra arrays.

Conclusion

The optimal solution is fast and uses no extra space. It’s the best approach for interviews and large datasets.

Final Thoughts

The “Missing And Repeating” problem is a great example of how to optimize your solution step by step. Start with brute force to understand the basics, then use hashing for speed, and finally use maths for the most efficient answer.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.