Minimum number of subsets with distinct elements

You are given an array of n-element. You have to make subsets from the array such that no subset contain duplicate elements. Find out minimum number of subset possible.

Examples : 

Input : arr[] = {1, 2, 3, 4}
Output :1
Explanation : A single subset can contains all 
values and all values are distinct
Input : arr[] = {1, 2, 3, 3}
Output : 2
Explanation : We need to create two subsets
{1, 2, 3} and {3} [or {1, 3} and {2, 3}] such
that both subsets have distinct elements.

We basically need to find the most frequent element in the array. The result is equal to the frequency of the most frequent element. Since we have to create a subset such that each element in a subset is unique that means that all the repeating elements should be kept in a different set. Hence the maximum no subsites that we require is the frequency of the maximum time occurring element.

Ex -> { 1 , 2 , 1 , 2 , 3 , 3 , 2 , 2 }
here
Frequency of 1 -> 2
Frequency of 2 -> 4
Frequency of 3 -> 2

Since the frequency of 2 is maximum hence we need to have at least 4 subset to keep all the 2 in different subsets and rest of element can be occupied accordingly.

A simple solution is to run two nested loops to count frequency of every element and return the frequency of the most frequent element. Time complexity of this solution is O(n²).

A better solution is to first sort the array and then start count number of repetitions of elements in an iterative manner as all repetition of any number lie beside the number itself. By this method you can find the maximum frequency or repetition by simply traversing the sorted array. This approach will cost O(nlogn) time complexity 

Implementation:

2

Time Complexity: O(n²)
Auxiliary Space: O(1)
 
An efficient solution is to use hashing. We count frequencies of all elements in a hash table. Finally we return the key with maximum value in hash table.

Implementation:

2

Time Complexity: O(n)
Auxiliary Space: O(n)

Example in c:

Approach:

Initialize a hash set to store distinct elements and a variable, count, to zero.

Iterate over all elements of the array.

For each element, check if it is already present in the hash set using the following conditions:

If the element is not present, add it to the hash set.
If the element is present, increment the count and reset the hash set.
Finally, return the count.

Minimum number of subsets with distinct elements: 8

The time complexity of this approach is O(n^2) since we use a loop within a loop to check for distinct elements. 

The space complexity is O(n) since we use a hash set to store distinct elements.

Approach:

At first, Initialize a DP array of size n, where n is the length of the input array. Now, we know dp[i] represents the minimum number of subsets required up to the i-th element of the given array.
Initialize a set to keep track of distinct elements seen so far. This set will be used to check for duplicate elements.
Initialize dp[0] as 1, since the first element itself forms a subset. Iterate through the array starting from the second element (i = 1) to the last element (i = n-1):Check if the current element is already present in the set.
If it is not present, add it to the set and set dp[i] = dp[i-1].
If it is present, increment dp[i] by 1 to account for a new subset required.
Clear the set and add the current element to start a new subset.
The final answer will be dp[n-1], representing the minimum number of subsets required to cover all the distinct elements.

Minimum number of subsets: 1
Minimum number of subsets: 2

 Time complexity : O(n), where n is the size of the input array.

 Auxiliary Space: O(n) as we have used the DP array to store intermediate results.