Find the lost element from a duplicated array

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:

  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.

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;
}
Try It

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.

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;
}
Try It


Next > < Prev
Scroll to Top