Find Minimum number of subsets with distinct elements in Java

Hello everyone, in this article, I will show you guys how to find minimum number of subsets with distinct elements in Java with simple examples. I have shown the source code with output for a better understanding. So let’s start this article with a brief introduction on subset.

Subset

A set A is a subset of another set B if all the elements in A belong to B also.

For example:

Input:
S = {a, b, c}
Output:
{}, {a} , {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}

Now focus on our main topic of this article. According to the title we have to find the minimum number subsets where no subset contains duplicate elements.

For example:

Input : arr[] = {10, 20, 30, 40}
Output :1
Explanation : A single subset can contains all 
values and all values are distinct

Input : arr[] = {10, 20, 30, 30}
Output : 2
Explanation : We need to create two subsets
{10, 20, 30} and {30} [or {10, 30} and {20, 30}] such
that both subsets have distinct elements.

To find this we basically have to find the frequency of the element in an array.

The simple approach is to run two loops so that we can count the frequency of each element in the array and return the frequency of the most frequent element. O(n2) is the time complexity.

The better approach is to first sort the array and then count the remaining elements in the array. This method will take O(nlogn) time complexity.

Java program to find Minimum number of subsets with distinct elements

Code Implementation is given below.

public class subset{ 
  
    public static int subset(int ar[], int n) 
    { 
        int res = 0; 

        Arrays.sort(ar); 

        for (int i = 0; i < n; i++) { 
            int count = 1; 

            for (; i < n - 1; i++) { 
                if (ar[i] == ar[i + 1]) 
                    count++; 
                else
                    break; 
            } 

            res = Math.max(res, count); 
        } 
  
        return res; 
    }       
}

In the above code, first, take the input and initialize res = 0. Then sort the array and traverse the input array and find the maximum frequency. For each number find its repetition and update the result as res.

Another way to solve this problem is by using hashing. First, we have to count the frequency of the elements in the table and then we can return the key of the maximum value in the hash table.

Code Implementation is shown below.

static int subset(int arr[], int n) 
{  
    HashMap<Integer, Integer> s = new HashMap<>();  
    for (int i = 0; i < n; i++)  
        s.put(arr[i],s.get(arr[i]) == null?1:s.get(arr[i])+1); 
      
    int res = 0; 
    for (Map.Entry<Integer,Integer> e : s.entrySet())  
    res = Math.max(res, e.getValue()); 
  
    return res; 
} 
//Main function
public static void main(String[] args)  
{ 
    int arr[] = {1, 2, 3, 3}; 
    int n = arr.length; 
    System.out.println( subset(arr, n)); 
  
} 

Output

2

So that’s it for this tutorial. I hope, this article is helpful for you and you have understood the logic behind this program.

Mention below your comments, if you find any mistake in the article or to share more information related to the topic of this article.

Leave a Reply

Your email address will not be published. Required fields are marked *