Missing And Repeating

Last updated: 8th Sept, 2020

Problem Statement

Given an unsorted array of size N of positive integers. One number 'A' from set {1, 2, …N} is missing and one number 'B' occurs twice in array. Find these two numbers.
Also, expected solution is O(n) time and constant extra space.

Example 1:

2
2
2 2
3
1 3 3

>> 2 1
>> 3 2

Example 2:

3
2
1 1
3
2 2 1

>> 1 2
>> 2 3

Method - 1:

In the above program we are supposed to find the duplicate number and the number missing the the range of N with a time complexity not exceeding O(n).
The inputs involved in the above problem are T that represents the testcases, N the total number of elements in array, Arr is the list of elements. Initialize another a new variable with list of size Arr containing 0's. The problem is solved by looping through each elements in the array. While traversing, the value of every element of Arr is used as an index and the value at this index is marked as negative indicate that the value is visited. If any element is already marked negative then this is the repeating element. To find the missing element, traverse the array again until an element that is not marked negative is found that is to look for a positive value.

Complexity Analysis :

Time Complexity- O(n)
Space Complexity- O(n)

Pseudocode :
PROGRAM missing_and_repeat
       INPUT : Read T, N, Arr
       SET B = 0
       SET A = 0
       FOR each element in Arr
             IF T[element] >= 0 THEN
                   T[element] = -1

             ELSE
                   B = element
             END IF
      END FOR
       FOR i from 1 to N + 1 // i += 1
             IF T[i] = 0
                   A = i
                   BREAK
             END IF
       END FOR
       PRINT B, A
END

Python Code

class solution:

    // method to find the missing and repeating number
    def missing_and_repeat(self, T):

        for _ in range(T):
            // number of integers in the array
            n=int(input())
            Arr=(int(i) for i in input().split())
            T=[0] * (n + 1)
            for i in Arr:
                if(T[i] >= 0):
                    T[i] = -1
                else:
                    B = i
            for i in range(1, n+1):
                if(T[i] == 0):
                    A = i
                    break
            print(B, A)

// Creating object of solution class
sol = solution()
sol.missing_and_repeat(int(input()))

Method - 2:

In the above method we subtract the sum of the elements in the list Arr and sum of element in set(Arr) (set(Arr) eliminates duplicate element) to obtain the repeating element. The missing elements is found by subtracting sum of all integers from 1 to n which can be represented in general form as n x (n + 1) / 2 and sum of set(Arr). The above code is less efficient when compared to that of the first one. This code does not meet the memory requirements.

                          Python Code
                          class solution:

    // method to find the missing and repeating number
    def missing_and_repeat(self, T):

        for _ in range(T):
            // number of integers in the array
            n=int(input())
            Arr=[int(i) for i in input().split()]
            print(sum(Arr) - sum(set(Arr)), int(n*(n+1)/2 - sum(set(Arr))))
// Creating object of solution class
sol = solution()
sol.missing_and_repeat(int(input()))
                        