The question is to find the Minimum Number of Subsets with Distinct Elements.
You will be handed an n-element array. You must divide the array into subsets so that no two subsets contain the same elements. Determine the minimum number of subsets feasible.
Input : arr[] = {10, 40, 30, 50}
Output: 1
Explanation: A single subset can contain all values and all values are distinct
Input : arr[] = {10, 20, 20, 30}
Output: 2
Explanation: We need to create two subsets
{10, 20, 30} and {20} [or {10, 20} and {20, 30}] such that both subsets have distinct elements.
Thus, we only need to discover the array's most frequent entry. The result will be equal to the frequency of the most frequent element present in the array.
Naive Approach
Running two nested loops to count the frequency of each element and return the frequency of the most frequent element is a straightforward method. This solution has an of time complexity O(n2). This is the brute force approach to solve the above problem.
ALGORITHM
A better technique is to sort the array first, then
iteratively count the number of repetitions of elements, as all repetitions of any number lie beside the number itself.
By traversing the sorted array, you can find the maximum frequency or repetition with this method.
C++ CODE
Implementation of code in C++ to find the Minimum Number of Subsets with Distinct Elements.
#include <bits/stdc++.h>
using namespace std;
int subsetCount(int arr[], int n)
{
int ans = 0;
sort(arr, arr + n);
for (int i = 0; i < n; i++) {
int count = 1;
for (int j=i+1; j < n; j++) {
if (arr[i] == arr[j])
count++;
else
break;
}
ans = max(ans, count);
}
return ans;
}
// Driver code
int main()
{
int arr[] = {10, 20, 40, 30, 30, 40, 40};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The minimum no. of subsets required are: " << subsetCount(arr, n);
return 0;
}
OUTPUT
The minimum no. of subsets required are: 3
JAVA CODE
Implementation of code in Java to find the Minimum Number of Subsets with Distinct Elements.
import java.util.*;
import java.lang.*;
public class work{
public static int subset(int ar[], int n)
{
int ans = 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;
}
ans = Math.max(ans, count);
}
return ans;
}
// Driver function
public static void main(String argc[])
{
int arr[] = {10, 20, 40, 30, 30, 40, 40};
int n = 7;
System.out.println(subset(arr, n));
}
}
OUTPUT
3
PYTHON CODE
Implementation of code in Python to find the Minimum Number of Subsets with Distinct Elements.
def subsetCount(arr, n):
ans = 0
arr.sort()
for i in range(0, n) :
count = 1
for j in range(i+1, n):
if arr[i] == arr[j]:
count+=1
else:
break
ans = max(ans, count)
return ans
# Driver code
arr = [10, 20, 40, 30, 30, 40, 40]
n = len(arr)
print(subsetCount(arr, n))
OUTPUT
3
Time Complexity
The time complexity of this approach is O(n^2) since we are sorting the array first and then iteratively counting the repetitions of the elements using two for loops.
Space complexity
The space complexity is O(1) since we are not using any extra space apart from some variables to store the result.
Optimal Approach
Hashing is a cost-effective solution. In a hash table, we count the number of times each entry appears. Finally, we return the hash table key with the highest value.
ALGORITHM
Define a map, count the frequency of each element of the array, and store the frequency in the map.
Put output at 0.
Navigate the map to determine the maximum between each key value and the output, then store that information in the output.
Return the value of output.
Let’s understand it step-wise through an example:
Let the array be
arr[] = {10, 20, 40, 30, 30, 40, 40};
The first thing we need to do is to count the occurrences of each element.
So for that, we are using a map, say, mp.
In mp, we will store the frequency of each element.
Therefore, the map will look something like this after the completion of the loop. mp = {10:1, 20:1, 30:2, 40:3}
Now we need to make subsets such that no two subsets contain the same elements.
Now the subsets that will be formed will look something like this: ({10, 20, 30, 40}, {30, 40}, {40}).
Here we can see that the number of subsets formed is equal to the highest frequency. The highest frequency is equal to the frequency of element 40 in the map.
Therefore the answer will be 3. (the maximum frequency of the element is the given array)
To find out the maximum frequency, we are using an “output” variable and initializing with zero, then running a loop and comparing the maximum between key-value and output.
C++ CODE
Implementation of code in C++ to find the Minimum Number of Subsets with Distinct Elements.
#include <bits/stdc++.h>
using namespace std;
int subsetCount(int arr[], int n)
{
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
int ans = 0;
for (auto i : mp)
ans = max(ans, i.second);
return ans;
}
/* Driver code */
int main()
{
int arr[] = {10, 20, 40, 30, 30, 40, 40};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The minimum no. of subsets required are " << subsetCount(arr, n)<<". ";
return 0;
}
OUTPUT
The minimum no. of subsets required are 3.
JAVA CODE
Implementation of code in Java to find the Minimum Number of Subsets with Distinct Elements.
import java.util.HashMap;
import java.util.Map;
class MinimumSubsets
{
public static int getMinSubset(int arr[], int n)
{
HashMap<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++)
mp.put(arr[i],mp.get(arr[i]) == null?1:mp.get(arr[i])+1);
int output = 0;
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
output = Math.max(output, entry.getValue());
return output;
}
public static void main(String[] args)
{
int arr[] = {10, 20, 40, 30, 30, 40, 40};
int n = arr.length;
System.out.println( getMinSubset(arr, n));
}
}
OUTPUT
3
PYTHON CODE
Implementation of code in Python to find the Minimum Number of Subsets with Distinct Elements.
def subsetCount(arr, n):
mp = {i:0 for i in range(10)}
for i in range(n):
mp[arr[i]] += 1
ans = 0
for key, value in mp.items():
ans = max(ans, value)
return ans
# Driver code
if __name__ == '__main__':
arr = [10, 20, 40, 30, 30, 40, 40]
n = len(arr)
print(subsetCount(arr, n))
OUTPUT
3
Time Complexity
We've used an unordered map or hash map in this case, which allows for insertion, deletion, and updating in O(1). As a result, we get a linear complexity of O(n), where "n" is the number of array entries.
Space Complexity
Because we're storing key and value pairs, there will be a maximum of n pairs, giving us O(n) space complexity, where "n" is the array's size. As a result, we can say that the algorithm for finding the smallest number of unique subsets has a linear space complexity solution.
Frequently Asked Questions
What are subsets of an array?
A subset of an array is similar to a subset of a set. We print all the possible combinations of the array using each element (including phi), meaning no elements of the array.
What will be the time complexity of the Naive Approach?
The time complexity of the naive approach is O(nlogn) as it consists of two loops and we sorted the array.
What will be the space complexity of the Naive Approach?
The space complexity of the naive approach is O(1) as we don't require any extra space for computing the result.
What is the time complexity of the Optimal Approach?
The time complexity of the optimal approach is O(n) as we are using unordered_map here.
What is the space complexity of the Optimal Approach?
The space complexity of the optimal approach is O(n) as we require extra space, ie, we're storing key and value pairs, and there will be a maximum of n pairs.
Conclusion
In this article, we have extensively discussed the problem of, Minimum Number of Subsets with Distinct Elements. We hope this blog has helped you understand this sum.
117+ registered 