# 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<<"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;
}
``````