Home » Technical Interview Questions » Array Interview Questions » Find the Lost Element From a Duplicated Array

Find the Lost Element From a Duplicated Array


Reading Time - 5 mins

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:

  1. If there is only one element in array A, then that element is missing in B, return the element.
  2. If the first element and not equal in A and B then the 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 the binary search in array A and get mid = (high + low)/2.
  4. If A[mid] = B[mid] then search for an element in the right part by making low as mid.
  5. Else, search for an element in the left part by making high as mid.
  6. End the loop, when low = high – 1 and return A[mid] which is the missing element.
READ  Count pairs from two sorted arrays whose sum is equal to a given value x

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.

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.

READ  First Bad Version

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:

  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.

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
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions