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 lost element from a duplicated array.

## Example

**Input**

5

A[] = {1, 6, 4, 8, 9};

B[] = {6, 4, 8, 9};

**Output**

1

## Approach 1

### Algorithm

If elements are in the same order,

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

**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 element and not equal in A and B then the 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 the binary search in array A and get mid = (high + low)/2.
- If A[mid] = B[mid] then search for an element in the right part by making low as mid.
- Else, search for an element in the left part by making high as mid.
- End the loop, when low = high â€“ 1 and return A[mid] which is the missing element.

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

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

### C++ Program for Find the Lost Element From a Duplicated Array

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

Missing Element: 1

**Note:** Assuming the elements in the same order in both A and B arrays.

### Complexity Analysis for Find the Lost Element From a Duplicated Array

**Time Complexity **

**O(logn) **where n is the size of the array. Here we apply a** binary search** which leads us to logn time complexity.

#### Space Complexity

**O(1)** because we use a few variables only to find the solution.

## Approach 2

### Algorithm

If elements in arrays are not in the same order,

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

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

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

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

### C++ Program for Find the Lost Element From a Duplicated Array

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

Missing element: 1

### Complexity Analysis for Find the Lost Element From a Duplicated Array

**Time Complexity **

**O(n) **where n is the size of the array. Here we traverse the array exactly one time which means the time complexity will be O(n).

#### Space Complexity

**O(1)** because we use a few variables only to find the solution.