Repeat and missing number in array

Written by

studymite

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&lt;&lt;"Missing Num : "&lt;&lt;x&lt;&lt;endl;
     	cout&lt;&lt;"Duplicate Num : "&lt;&lt;y&lt;&lt;endl;
      	break;
   }

} }

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