# Remove Minimum Number of Elements Such That no Common Element Exist in both Array  Difficulty Level Easy
Frequently asked in Alation MetLife Oxigen Wallet ServiceNow Spotify
Array Hash

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.

Check for Palindrome after every character replacement Query

## 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).