Find minimum number of subsets with distinct elements in C++

Hello guys, today we will be finding the minimum number of subsets with distinct elements for a given array.

Minimum number of subsets with distinct elements

So to solve this, we should find the element which repeats the maximum number of times. The frequency of times this element repeats will be the required answer.

For example, let us consider an array having elements: {1, 2, 3, 4, 1, 2, 3, 1, 2, 1}. In this array, we can see that 1 is repeated 4 times. We can break the above array into 4 subsets: {1, 2, 3, 4}, {1, 2, 3}, {1, 2}, and {1}.

Let’s implement the problem in C++.

We’ll iterate over the array and use a map to store the distinct elements of the array as keys and their respective count as values. After the iteration, we’ll find out the count of the element repeated the maximum number of times.

Code:

#include <iostream>
#include <map>

using namespace std;

int main() {
    cout << "Enter the number of elements: ";
    int n;
    cin >> n;

    cout << "Enter the array: ";
    int arr[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int temp = arr[i];

        if (counts[temp]) {
            counts[temp]++;
        } else {
            counts[temp] = 1;
        }
    }

    int max_count = -1;
    for (auto itr = counts.begin(); itr != counts.end(); ++itr) {
        if (max_count < itr->second)
            max_count = itr->second;
    }

    cout << "The minimum number of subsets with distinct element is: " << max_count << endl;   

    return 0;
}

Output:

Enter the number of elements: 10
Enter the array: 1 2 3 4 1 2 3 1 2 1
The minimum number of subsets with distinct element is: 4

See also:

• Frequency of character in a string
• Check if a key is present in a map