Find Missing and Repeating Number


This video explains how to find missing and repeating number in an array. I have shown 3 methods. The first one is naive approach which is done using sorting technique. The second one is better which makes use of buckets or hashing. The third one is the efficient approach which makes use of mathematical formula or tricks. Code is explained for the better approach at the end of the video so do watch till the end. CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below.

#include <iostream>
using namespace std;

int main() {
	int tc;
	cin>>tc;
	while(tc--) //test cases
	{
	    int N;
	    cin>>N;
	    //Input all N eleemnts
        int arr[N];
        int repeating,missing;
        bool present[N+1] = {false};  //Checks which numbers are present
        for(int i=0;i<N;++i)
        {
            cin>>arr[i];
            if(present[arr[i]]==true)
                repeating = arr[i];
            present[arr[i]] = true;
        }
        
        for(int i=1;i<=N;++i)
        {
            if(present[i]==false)
            {
                missing = i;
                break;
            }
        }
        
        cout<<repeating<<" "<<missing<<"\n";
	}
	return 0;
}

Write a comment