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

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

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