Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Example
3.
Naive Approach
4.
Optimal Approach
5.
Frequently Asked Questions
5.1.
What are subsets of an array?
5.2.
What will be the time complexity of the Naive Approach?
5.3.
What will be the space complexity of the Naive Approach?
5.4.
What is the time complexity of the Optimal Approach?
5.5.
What is the space complexity of the Optimal Approach?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Minimum Number of Subsets with Distinct Elements

Author Komal Shaw
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Problem Statement

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.

Recommended topic about, kth largest element in an array and  Euclid GCD Algorithm

Example

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.

Minimum number of subsets with distinct elements example
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

  1. A better technique is to sort the array first, then
     
  2. iteratively count the number of repetitions of elements, as all repetitions of any number lie beside the number itself.
     
  3. 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

  1. Define a map, count the frequency of each element of the array, and store the frequency in the map.
     
  2. Put output at 0.
     
  3. Navigate the map to determine the maximum between each key value and the output, then store that information in the output.
     
  4. 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};

 

  1. The first thing we need to do is to count the occurrences of each element.
     
  2. So for that, we are using a map, say, mp.
     
  3. In mp, we will store the frequency of each element.
     
  4. Therefore, the map will look something like this after the completion of the loop.
    mp = {10:1, 20:1, 30:2, 40:3}
     
  5. Now we need to make subsets such that no two subsets contain the same elements.
     
  6. Now the subsets that will be formed will look something like this: ({10, 20, 30, 40}, {30, 40}, {40}).
     
  7. 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.
     
  8. Therefore the answer will be 3. (the maximum frequency of the element is the given array)
     
  9. 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.

If you want to learn more, check out our articles on Distribute maximum number of chocolates amongst X studentsWinner of Tic-tac-toereduce-array-size-to-the-half.

Recommended Problem - Merge K Sorted Arrays

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc.

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!

Previous article
Rearrange Positive and Negative Numbers With Constant Extra Space | Part 1
Next article
Find the first, second, and third minimum elements in an array
Live masterclass