Repeat and missing number in array

Problem

You are given an array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Print A and B.

Brute Force Approach

Using sorting

Sort the given array and traverse the array. If the element is not equal to i+1, then the i+1 is missing and arr[i] is duplicate.

TC – O(NlogN)

SC – O(1)

Better Approach

Using HashMap

Put all the array elements in the hashmap with their occurrence count. Iterate from 1 to n and check their occurrence count in the map, if count is greater than 1 then the number is duplicate else if the key doesn’t exist means the element is missing.

TC – O(N)

SC – O(N)

Optimal Approach

Using swap sort

We’ll check if the element is not at its right place swap it with its correct position.

#include<bits/stdc++.h>
using namespace std;

void printMissingAndDuplicateNum(int arr[],int arrSize){
  int i = 0;
  
  while(i < arrSize){
    if(arr[i] != arr[arr[i]-1]) 
      swap(arr[i], arr[arr[i]-1]);
    } else {
      i++;
    }
  }
	
  for(int i = 0; i<arrSize; i++){
  	cout<<arr[i]<<" ";
  }
  cout<<endl;
  for(int i = 0; i<arrSize; i++){
  	if(arr[i] != i+1){
    	cout<<"Missing Number : "<< i + 1<<endl;
      	cout<<"Duplicate Number : "<< arr[i]<<endl;
    }
  }
}

int main(){
  int arr[] = {1,2,2,4};
  int arrSize = sizeof(arr)/sizeof(arr[0]);
  printMissingAndDuplicateNum(arr, arrSize);
  return 0;
}

TC – O(N) // in worst case first element is swapped with all other

SC – O(1) 

Using Bit Manipulation(If the array is read-only)

First, we’ll find the xor of 1 to n and arr[0] to arr[n-1].  Then find the right significant(RSB) bitmask of xor, and now divide the elements into two parts one with RSB set and the other with RSB not set.

#include<bits/stdc++.h>
using namespace std;

void printMissingAndDuplicateNum(int arr[],int arrSize){
   int xorr = 0;
   for(int i = 0 ; i < arrSize; i++){
       xorr ^= arr[i];
       xorr ^= (i + 1);
   }
  
   int rightSignificantBitMask = xorr & (-xorr);
   
   int x = 0;
   int y  = 0;
   for(int i = 0 ; i < arrSize; i++){
       if((rightSignificantBitMask & arr[i]) == 0){
           x ^= arr[i];
       }else{
           y ^= arr[i];
       }
   }
   
   for(int i = 1 ; i <= arrSize; i++){
       if((rightSignificantBitMask & i) == 0){
           x ^= i;
       }else{
           y ^= i;
       }
   }
   
   for(int i = 0 ; i < arrSize; i++){
       if(arr[i] == x){
         	cout<<"Missing Num : "<<y<<endl;
         	cout<<"Duplicate Num : "<<x<<endl;
           	break;
       }
       
       if(arr[i] == y){
         	cout<<"Missing Num : "<<x<<endl;
         	cout<<"Duplicate Num : "<<y<<endl;
          	break;
       }
   }
}

int main(){
  int arr[] = {1,2,2,4};
  int arrSize = sizeof(arr)/sizeof(arr[0]);
  printMissingAndDuplicateNum(arr, arrSize);
  return 0;
}