Find Missing And Repeating

(Geeks for Geeks : Medium Level)

Given an unsorted array Arr 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.

Example 1:

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

Example 2:

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

I am going to discuss the most optimised approach here and that is using the xor operation.

This is the code below and now I will dry run an example to help you understand of the approach and concept better.

class Solution{
public:
    int *findTwoElement(int *arr, int n) {
        // Step 1 =  Find xor of all elements in the array 
        // Step 2 = Find xor of step1 ans with numbers from 1 to n 
        int xorr = 0;
        for(int i=0;i<n;i++)
        {
            xorr^=arr[i];
            xorr^=(i+1);
        }
        
        // Now to find the significant bit , perfrom the below operation 
        int rightSBit = xorr & (-xorr);
        int x = 0;
        int y = 0;
        
        // Now numbers with same significant bit in the given array, xor them together 
        for(int i=0;i<n;i++)
        {
            if((rightSBit & arr[i])==0)
                x^=arr[i];
            else
                y^=arr[i];
        }
        
        // Similarly numbers from 1 to n with the same significant bits, xor them together 
        for(int i=1;i<=n;i++)
        {
            if((rightSBit & i)==0)
                x^=i;
            else
                y^=i;
        }
        
        int *ans = new int(2);
        
        // Final step : If x is found in array means it is repeating and y is missing & vice versa 
        for(int i=0;i<n;i++)
        {
            if(arr[i]==x)
            {
                ans[0]=x;
                ans[1]=y;
            }
            
            if(arr[i]==y)
            {
                ans[0]=y;
                ans[1]=x;
            }
        }
        return ans;
        
    }
};
Let us for example take arr = {1 3 3}
Step 1 : Find xor of all elements 
         xorr = 1^3^3 = 1 
Step 2 : Find the xor of all elements from 1 to n with xorr,
         xorr = 1^1^2^3 = 1 
Step 3 : Now find , rightSBit = 1 & (-1)
         To find what -1 is written in binary follow the below steps 
         1. Ignore the sign and write its binary equivalent , 1
         2. Now add 1 , it becomes = 10 in binary (2)
         3. Now negate it , ~10 = 01 which is again 1
         4. so rightSBit = 1&1 = 1
Step 4 : Now find rightSBit & arr[i]
         1&1 = 1, 1&3 = 1, 1&3 =1
         so x will be 0, 
         y = 1^3^3 = 1
Step 5 : Now find rightSBit & i
         1&1 = 1, 1&2 = 0, 1&3 = 1
         x = 0^2 = 2
         y = 1^1^3 = 3
Step 6 : Now traversing the loop, 
         y is present in the array so, y is the reeating element and 
         x is the missing element.
Time Complexity - O(n)
Space Complexity - O(1)

Link to my GitHub Repository for notes : https://github.com/BharatiSukanya/Striver_Sheet_Notes

Hope this helps! Keep coding!

Useful resouces :

1. https://practice.geeksforgeeks.org/problems/find-missing-and-repeating2512/1#
2. https://www.youtube.com/watch?v=5nMGY4VUoRY&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=3
3. https://docs.google.com/document/d/1SM92efk8oDl8nyVw8NHPnbGexTS9W-1gmTEYfEurLWQ/edit

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕