# Find the lost element from a duplicated array

0
177

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

1. If there is only one element in array A, then that element is missing in B, return the element.
2. If the first elements and not equal in A and B then first element itself is missing, return the first element of A.
3. 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.
4. If A[mid] = B[mid] then search for element in right part by making low as mid.
5. Else, search for element in left part by making high as mid.
6. 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:

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

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

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

1. Initialize Missing_element = 0
2. Use XOR on all the elements in the array with Missing_element
3. 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.

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