Most attainable measurement of subset following the given constraints

Given an array arr[] of measurement n, the duty is to seek out the most attainable measurement x of a subset such that there are precisely two subsets of the identical measurement that ought to observe the beneath constraints:

• The first subset ought to include distinct components (i.e., all components within the first subset are distinctive) and it may need one aspect in widespread with the second subset.
• The second subset ought to include all identical components (i.e., all components within the second subset are equal)

Examples: 

Enter: arr[] = {4, 2, 4, 1, 4, 3, 4}
Output: 3
Clarification: It’s attainable to assemble two subsets of measurement 3: the primary subset is [1, 2, 4] and the second subset is [4, 4, 4]. Be aware, that there are another methods to assemble two legitimate groups of measurement 3.

Enter: arr[] = {1, 1, 1, 3}
Output: 2
Clarification: It’s attainable to assemble two subsets of measurement 2: the primary subset is [1, 3] and the second subset is [1, 1].

Method: Implement the thought beneath to unravel the issue:

• Let’s suppose we’re in a position to make two subsets utilizing the given constraints with measurement x, So, to be able to discover the utmost measurement attainable, we retailer the present measurement x in our reply variable and replace low with mid + 1. 
• If we weren’t in a position to create two subsets utilizing the given constraints with measurement x, it’s certain we might not have the ability to create two subsets from measurement x + 1 to n, so we might replace excessive as mid – 1.
• We will get to know whether it is attainable to type two subsets utilizing the given constraints is feasible or not utilizing the map, we will retailer the frequency of every aspect within the map and if the frequency of any aspect is larger than or equal to the dimensions we’re checking on and in addition to the dimensions of the map-1 must be higher than or equal to the dimensions we’re checking on, we might subtract the map measurement by -1 as a result of it shops the depend of distinct components and 1 aspect is already used to create the subset which accommodates all identical components.

Observe the steps talked about beneath to implement the thought:

• Initialize low as 0 and excessive as n/2 initially.
• Calculate mid and test if is it attainable to create two subsets utilizing the given constraints
• If attainable, replace ans to mid (present measurement) and low to mid +1.
• Else, replace excessive to mid – 1.
• Use a map to retailer the frequency of every aspect and to know the potential for subset formation.
• If the dimensions of the map – 1 is larger than or equal to the dimensions we’re checking on and any aspect is showing greater than or equal to the dimensions we’re checking on, then it’s at all times attainable to type two subsets so return true else false.

Under is the implementation of the above strategy:

// C++ code to implement the strategy
#embody <bits/stdc++.h>
utilizing namespace std;

// Perform for checking if is it attainable
// to create two subsets utilizing the given
// constraints with the dimensions mid
bool is_possible(unordered_map<int, int>& mpp, int mid)
{
    bool flag1 = false;
    bool flag2 = false;
    bool flag = false;
    for (auto it : mpp) {
        if (it.second >= mid) {
            flag1 = true;
            if (it.second > mid)
                flag2 = true;
        }
    }

    int measurement = mpp.measurement() - 1;
    if (flag2)
        measurement += 1;

    return flag1 && measurement >= mid;
}

// Perform for locating out the
// most measurement
int maximum_size(vector<int>& arr, int n)
{

    // Declare map for storing
    // the frequency of every aspect
    unordered_map<int, int> mpp;
    for (auto it : arr) {
        mpp[it]++;
    }

    // Vary of binary search
    int low = 0;
    int excessive = n / 2;

    // Retailer the utmost measurement
    int ans = 0;

    whereas (low <= excessive) {

        // Calculating mid
        int mid = (low + excessive) >> 1;

        // If it attainable to create two
        // subsets, retailer mid in ans and
        // replace low as mid+1 to be able to
        // discover the utmost attainable measurement
        if (is_possible(mpp, mid)) {

            ans = mid;
            low = mid + 1;
        }

        // If it isn't attainable to create
        // two subsets, it might not be
        // attainable to create subsets from
        // measurement mid to n thus, replace excessive
        // as mid -1
        else {
            excessive = mid - 1;
        }
    }

    // Return the utmost attainable measurement
    return ans;
}

// Driver code
int primary()
{
    vector<int> arr = { 4, 2, 4, 1, 4, 3, 4 };
    int n = arr.measurement();

    // Perform name
    cout << maximum_size(arr, n);
    return 0;
}

Time Complexity: O(N)
Auxiliary Area: O(N)

Associated Articles: