Find the lost element from a duplicated array TutorialCup

Table of Contents

Problem Statement

Given two arrays A and B, one array is a 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

5
1 6 4 8 9
6 4 8 9

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.

Implementation

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.

Java Program for Find the Lost Element From a Duplicated Array

import java.util.Scanner;
class sum
{
    //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
    public static 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 
    public static void FindMissing(int A[], int B[], int M, int N)
    {
        if(N == M-1)
        {
            System.out.println("Missing Element: " + FindMissingInB(A, B, M));
        }
        else if(M == N-1)
        {
            System.out.println("Missing Element: " + FindMissingInB(B, A, N));
        }
        else
        {
            System.out.println("Invalid!");
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int m = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[m];
        for(int i=0;i<m;i++)
        {
            b[i] = sr.nextInt();
        }
        FindMissing(a,b,n,m); 
    }
}

5
1 6 7 3 2
1 6 7 2

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.