# Find Missing And Repeating

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:**

- Sort the input array.
- 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:**

- Create a temp array temp[] of size n with all initial values as 0.
- 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

- 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:**

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

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)