Select Page

Maximum possible size of subset following the given constraints

Team 1 - Programming
Published: January 25, 2023

#include <bits/stdc++.h>

using namespace std;

  

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 size = mpp.size() - 1;

    if (flag2)

        size += 1;

  

    return flag1 && size >= mid;

}

  

int maximum_size(vector<int>& arr, int n)

{

  

    

    

    unordered_map<int, int> mpp;

    for (auto it : arr) {

        mpp[it]++;

    }

  

    

    int low = 0;

    int high = n / 2;

  

    

    int ans = 0;

  

    while (low <= high) {

  

        

        int mid = (low + high) >> 1;

  

        

        

        

        

        if (is_possible(mpp, mid)) {

  

            ans = mid;

            low = mid + 1;

        }

  

        

        

        

        

        

        else {

            high = mid - 1;

        }

    }

  

    

    return ans;

}

  

int main()

{

    vector<int> arr = { 4, 2, 4, 1, 4, 3, 4 };

    int n = arr.size();

  

    

    cout << maximum_size(arr, n);

    return 0;

}

Source: www.geeksforgeeks.org