Find Missing And Repeating

Last updated: 29th Aug, 2020

Problem Statment

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. Note: If you find multiple answers then print the Smallest number found.

Example 1:

Input
2
2
2 2
3
1 3 3

Output:
2 1
3 2

Method:

Check if the absolute value of array element is greater than zero.
To find the repeating value if the absolute value of element of array minus one value is less then zero then absolute value of element of array minus one element of array will be negative.
Otherwise,print the absolute value of the element of array.
To find the missing value itirate through array if element of array is greater than zero then print index plus one.

Python Code


def repeat( arr, size): 
    for i in range(size): 
        if arr[abs(arr[i])-1] > 0: 
            arr[abs(arr[i])-1] = -arr[abs(arr[i])-1] 
        else: 
            print(abs(arr[i]),end=" ") 
              
    for i in range(size): 
        if arr[i]>0: 
            print(i + 1) 
test=int(input())
while test:
    n=int(input())
    arr = input().split()
    for i in range(len(arr)):
        arr[i] = int(arr[i])
    repeat(arr, n) 
    test-=1