## Given two arrays A and B, one array is duplicate of the other except one element. The one element is missing from either A or B. we need to find the missing element.

### Example

## Method 1

**Time Complexity : O(MlogN)**

## Algorithm

If elements are in same order,

**Step 1 :** create a function FindMissingInB where size of A is greater than size of B which means element is missing in B.

**Step 2 :** In FindMissingInB function:

- If there is only one element in array A, then that element is missing in B, return the element.
- If the first elements and not equal in A and B then first element itself is missing, return the first element of A.
- Else, initialize mid and low as the corner points of the array A and start binary search in array A and get mid = (high + low)/2.
- If A[mid] = B[mid] then search for element in right part by making low as mid.
- Else, search for element in left part by making high as mid.
- End the loop, when low = high – 1 and return A[mid] which is the missing element.

**Step 3 :** Create a new function FindMissing with conditions:

- If Size of A = Size of B + 1, print FindMissingInB(A,B)
- If Size of B = Size of A + 1, print FindMissingInB(B,A)
- Else, invalid input.

**Step 4 :** call the function on the given two input arrays to print the missing number.

### Algorithm working

## C++ Program

```
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//Function:
//Using binary search approch in finding the missing element
//where A[] is bigger array than B
//Assuming the elements in same order in both A and B
int FindMissingInB(int A[], int B[], int N)
{
//condition
//only one element in A and B is empty
if (N == 1)
{
return A[0];
}
//condition
//First element is missing
// special case, for first element missing
if (A[0] != B[0])
{
return A[0];
}
//condition
//element is in between
// Initialize low and high
int low = 0,high = N - 1;
while (low < high)
{
int mid = (low + high) / 2;
//mid elements are equal then search in right subarray
if (A[mid] == B[mid])
{
low = mid;
}
else //mid elements are not eqaul
{
high = mid;
}
// end when low = high -1
if (low == high - 1)
{
break;
}
}
//Missing element
return A[high];
}
//Checking conditions Size A > Size B or
void FindMissing(int A[], int B[], int M, int N)
{
if (N == M-1)
{
cout << "Missing Element: "<< FindMissingInB(A, B, M) << endl;
}
else if (M == N-1)
{
cout << "Missing Element: "<< FindMissingInB(B, A, N) << endl;
}
else
{
cout << "Invalid!"<<endl;
}
}
//Main Function
int main()
{
int A[] = {1, 6, 4, 8, 9};
int B[] = {6, 4, 8, 9};
int M = sizeof(A)/sizeof(int);
int N = sizeof(B)/sizeof(int);
FindMissing(A, B, M, N);
return 0;
}
```

## Method 2

**Time Complexity : O(M+N)**

## Algorithm

If elements in arrays are not in same order,

**Step 1 :** we create a function FindMissing to find the missing element.

**Step 2 :** In this function:

- Initialize Missing_element = 0
- Use XOR on all the elements in the array with Missing_element
- Missing_element = Missing_element ^ A[i] or B[i] for all elements.

**Step 3 :** The final value of Missing_element is the missing lost element.

**Step 4 :** call the function on the given arrays to print the missing element.

### Algorithm working

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
//using XOR on all the elements.
void FindMissing(int A[], int B[], int M,int N)
{
if (M != N-1 && N != M-1)
{
cout << "Invalid!";
return;
}
int MissingElement = 0;
for (int i=0; i<M; i++)
{
MissingElement = MissingElement^A[i];
}
for (int i=0; i<N; i++)
{
MissingElement = MissingElement^B[i];
}
cout << "Missing element: " << MissingElement;
}
//main function
int main()
{
int A[] = {4, 1, 5, 9, 7};
int B[] = {7, 5, 9, 4};
int M = sizeof(A)/ sizeof(int);
int N = sizeof(B)/ sizeof(int);
FindMissing(A, B, M, N);
return 0;
}
```