Home » Technical Interview Questions » Hashing Interview Questions » Remove Minimum Number of Elements Such That no Common Element Exist in both Array

# Remove Minimum Number of Elements Such That no Common Element Exist in both Array

Given two arrays A and B consisting of n and m elements respectively. Remove minimum number of elements such that no common element exist in both array and print the count of elements which removed.

## Example

Input:

A[]={ 1, 2, 1, 1}

B[]= {1, 1}

Output:

Minimum elements to remove from each array are 3.

## Main idea

Let’s say we have an element num which is common in both the arrays. Num appears X number of times in array A and Y number of times in array B. So to make the intersection of the two arrays null, we have three options:

1. Remove all the occurrences of num from array A.
2. Remove all the occurrences of num from array B.
3. Now, Remove all the occurrences of num from both A and B.

As we have to do a minimum number of operations, out of these three options, we will choose 1st option if X is less than Y, or 2nd option if Y is less than X.

To count the occurrences of each element in the arrays, we will use the hash table.

## Algorithm for Remove minimum number of elements

1. Initialize a variable ans which will store the answer.
2. Iterate over the arrays and store the occurrence of every element in a hash table for both arrays.
3. For each element num in the arrays, if X is the number of occurrence of num in A and Y is the number of occurrence of num in B, then add minimum(X, Y) to ans.
4. Return ans.

## Understand With an Example

Let’s say we have

A[]={2, 3, 2, 2, 0, 4}

B[]= {4, 4, 2, 20}

Now we make the hash table for the above arrays. For element 0, we will add a minimum(1, 0)=0 to the ans.

For element 2, we will add a minimum(3, 1)=1 to the ans.

Now, For element 3, we will add a minimum(1, 0)=0 to the ans.

For element 4, we will add a minimum(1, 2)=1 to the ans.

For element 20, we will add a minimum(0, 1)=0 to the ans.

Final ans=2.

## C++ Program for Remove minimum number of elements

```#include <bits/stdc++.h>
using namespace std;
int MinElementsToRemove(vector<int> &A, vector<int> &B)
{
unordered_map<int, int> count_A, count_B;
for (auto ele : A)
{
count_A[ele]++;
}
for (auto ele : B)
{
count_B[ele]++;
}
int ans = 0;
for (auto ele : count_A)
{
if (count_B.count(ele.first) == 1)
{
ans += min(count_B[ele.first], count_A[ele.first]);
}
}
return ans;
}
int main()
{
vector<int> A = {2, 3, 2, 2, 0, 4};
vector<int> B = {4, 4, 2, 20};
cout << "Minimum number of elements to remove from each array such that no common element exist in both array: " << MinElementsToRemove(A, B) << endl;
return 0;
}
```
`Minimum number of elements to remove from each array such that no common element exist between both array: 2`

## JAVA Program for Remove minimum number of elements

```import java.util.*;
public class Main
{
public static int MinElementsToRemove(int[] A, int[] B)
{
Map<Integer, Integer> count_A
= new HashMap<Integer, Integer>();
Map<Integer, Integer> count_B
= new HashMap<Integer, Integer>();
for (int i=0; i<A.length;i++)
{
Integer j =count_A.get(A[i]);
count_A.put(A[i], (j == null) ? 1 : j + 1);
}
for (int i=0; i<B.length;i++)
{
Integer j =count_B.get(B[i]);
count_B.put(B[i], (j == null) ? 1 : j + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : count_A.entrySet()){
if (count_B.get(entry.getKey())!=null)
{
ans += Math.min(count_B.get(entry.getKey()), count_A.get(entry.getKey()));
}
}
return ans;
}
public static void main(String[] args) {
int[] A = {2, 3, 2, 2, 0, 4};
int[] B = {4, 4, 2, 20};
System.out.println("Minimum number of elements to remove from each array such that no common element exist in both array: "+MinElementsToRemove(A, B));
}
}

```
`Minimum number of elements to remove from each array such that no common element exist between both array: 2`

## Complexity Analysis for Remove minimum number of elements

### Time complexity

As we iterate over both the arrays once, so the total time complexity is O(N+M).

READ  Smallest Subarray With all Occurrences of a Most Frequent Element

### Space complexity

We used two hash tables to store the frequency of elements for both the arrays, so the space complexity is O(N+M).

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions