Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Missing And Repeating – GeeksforGeeks Solution Explained
    Data Structures & Algorithms

    Missing And Repeating – GeeksforGeeks Solution Explained

    codeanddebugBy codeanddebug7 July 2025No Comments6 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of question named merge and repeat
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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() ≤ 106
    1 ≤ arr[i] ≤ arr.size()

    Contents:
     [show]
    • Brute Force Solution (Nested Loops)
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Better Solution (Hashing)
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Optimal Solution (Maths: Sum and Sum of Squares)
      • Intuition and Approach
      • Code Implementation
      • Code Explanation
      • Dry Run
      • Time and Space Complexity
      • Conclusion
    • Final Thoughts

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

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

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

    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.

    Join our Advance DSA COURSE

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

    Array Hard
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleMerge Without Extra Space – GeeksforGeeks Solution Explained
    Next Article Count Inversions – GeeksforGeeks Solution Explained
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025
    Data Structures & Algorithms

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025
    Data Structures & Algorithms

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (99)
      • Beginner (44)
      • Expert (28)
      • Intermediate (27)
    • Uncategorised (1)
    Recent Posts

    Reverse Pairs | Leetcode 493 | Optimal Merge Sort

    7 July 2025

    Count Inversions – GeeksforGeeks Solution Explained

    7 July 2025

    Missing And Repeating – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Without Extra Space – GeeksforGeeks Solution Explained

    7 July 2025

    Merge Intervals | Leetcode 56 | Brute Force and Optimal

    7 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.