Find Missing And Repeating

Given an unsorted array of size n. Array elements are in the range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers .

Example 2:

Input:
N = 3
Arr[] = {1, 3, 3}
Output: 3 2
Explanation: Repeating number is 3 and 
smallest positive missing number is 2.

Method 1 :

(Use Sorting)

Approach:

1. Sort the input array.
2. Traverse the array and check for missing and repeating.

 int findTwoElement(int arr[], int n) {
        sort(arr,arr+n);
        int repeat; int missing;
        for(int i=0;i<n-1;i++)
        {
            if(arr[i]==arr[i+1])
            {
                repeat=arr[i];
                
            }
            
        }
        
       int s=0;
        
        for(int i=0;i<n-1;i++)
        {
            if(arr[i+1]!=arr[i]+1 && arr[i+1]!=arr[i])
             {  missing =arr[i]+1;
             s++;
             }
        }
        
       if(s==0)
       missing=arr[0]-1;
       
       if(k[1]==0)
       missing=arr[n-1]+1;
        cout<<repeat<<" "<<missing;
    }

Time Complexity: O(nLogn)

Auxiliary Space: O(n)

Method 2

(Use count array)

Approach:

1. Create a temp array temp[] of size n with all initial values as 0.
2. Traverse the input array arr[], and do following for each arr[i]
   • if(temp[arr[i]] == 0) temp[arr[i]] = 1;
   • if(temp[arr[i]] == 1) output “arr[i]” //repeating
3. Traverse temp[] and output the array element having value as 0 (This is the missing element)

 int findTwoElement(int arr[n], int n) {
      
      
        int temp[n];
        
        for(int i=1;i<=n;i++)
        temp[i]=0;
        
        for(int i=0;i<n;i++)
        {
            if(temp[arr[i]]==1)
            {
                repeat=arr[i];
                
            }
            else
            temp[arr[i]]=1;
            
        }
        
        for(int i=1;i<=n;i++)
        { 
            if(temp[i]==0)
            missing=i;
        }
      
       cout<<repeat<<" "<<missing;

    }

Time Complexity: O(n)
Auxiliary Space: O(n)

the above approach can even solved using maps

Method 3:

 (Make two equations using sum and sum of squares)

Approach:

1. Let x be the missing and y be the repeating element.
2. Let N is the size of array.
3. Get the sum of all numbers using formula S = N(N+1)/2
4. Get product of all numbers using formula Sum_Sq = N(N+1)(2N+1)/6
5. Iterate through a loop from i=1….N
6. S = S- A[i]
7. Sum_Sq =Sum_Sq- (A[i]*A[i])
8. It will give two equations

x-y = S -------(1)
x^2 – y^2 = Sum_sq
x+ y = (Sum_sq/S)  -------------- (2)

solving equations 1 and 2 we will get x and y

 int repeatmiss(long long int a[],long long int n) { 

    long long int Sum_N = (len * (len+1) ) /2;
    long long int Sum_NSq = (len * (len +1) *(2*len +1) )/6; 
    long long int missingNumber=0, repeating=0; 
      
    for(int i=0;i<n; i++){ 
       Sum_N -= a[i]; 
       Sum_NSq -= (a[i]*a[i]); 
    } 
      
    missingNumber = (Sum_N + Sum_NSq/Sum_N)/2; 
    repeating= missingNumber - Sum_N; 
    cut<<repeating<<" "<<missingNumber;
      
} 

Time Complexity: O(n)
Auxiliary Space: O(1)