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.

Table of Contents

## 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:

- Remove all the occurrences of num from array A.
- Remove all the occurrences of num from array B.
- 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 1^{st} option if X is less than Y, or 2^{nd} 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

- Initialize a variable ans which will store the answer.
- Iterate over the arrays and store the occurrence of every element in a hash table for both arrays.
- 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.
- 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)**.

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