Given an unsorted array of size n. Array elements are in the range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers .

Example 2:

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

Method 1 :

(Use Sorting)

Approach:

1. Sort the input array.
2. Traverse the array and check for missing and repeating.

int findTwoElement(int arr[], int n) {
sort(arr,arr+n);
int repeat; int missing;
for(int i=0;i<n-1;i++)
{
if(arr[i]==arr[i+1])
{
repeat=arr[i];

}

}

int s=0;

for(int i=0;i<n-1;i++)
{
if(arr[i+1]!=arr[i]+1 && arr[i+1]!=arr[i])
{  missing =arr[i]+1;
s++;
}
}

if(s==0)
missing=arr[0]-1;

if(k[1]==0)
missing=arr[n-1]+1;
cout<<repeat<<" "<<missing;
}

Time Complexity: O(nLogn)

Auxiliary Space: O(n)

Method 2

(Use count array)

Approach:

1. Create a temp array temp[] of size n with all initial values as 0.
2. Traverse the input array arr[], and do following for each arr[i]
• if(temp[arr[i]] == 0) temp[arr[i]] = 1;
• if(temp[arr[i]] == 1) output “arr[i]” //repeating
3. Traverse temp[] and output the array element having value as 0 (This is the missing element)

int findTwoElement(int arr[n], int n) {

int temp[n];

for(int i=1;i<=n;i++)
temp[i]=0;

for(int i=0;i<n;i++)
{
if(temp[arr[i]]==1)
{
repeat=arr[i];

}
else
temp[arr[i]]=1;

}

for(int i=1;i<=n;i++)
{
if(temp[i]==0)
missing=i;
}

cout<<repeat<<" "<<missing;
}

Time Complexity: O(n)
Auxiliary Space: O(n)

the above approach can even solved using maps

Method 3:

(Make two equations using sum and sum of squares)

Approach:

1. Let x be the missing and y be the repeating element.
2. Let N is the size of array.
3. Get the sum of all numbers using formula S = N(N+1)/2
4. Get product of all numbers using formula Sum_Sq = N(N+1)(2N+1)/6
5. Iterate through a loop from i=1….N
6. S = S- A[i]
7. Sum_Sq =Sum_Sq- (A[i]*A[i])
8. It will give two equations
9. x-y = S -------(1)
x^2 – y^2 = Sum_sq
x+ y = (Sum_sq/S)  -------------- (2)

solving equations 1 and 2 we will get x and y

int repeatmiss(long long int a[],long long int n) {

long long int Sum_N = (len * (len+1) ) /2;
long long int Sum_NSq = (len * (len +1) *(2*len +1) )/6;
long long int missingNumber=0, repeating=0;

for(int i=0;i<n; i++){
Sum_N -= a[i];
Sum_NSq -= (a[i]*a[i]);
}

missingNumber = (Sum_N + Sum_NSq/Sum_N)/2;
repeating= missingNumber - Sum_N;
cut<<repeating<<" "<<missingNumber;

}

Time Complexity: O(n)
Auxiliary Space: O(1)

darkmode