Given an array arr[] of size n, the task is to find the maximum possible size x of a subset such that there are exactly two subsets of the same size that should follow the below constraints:
- The first subset should consist of distinct elements (i.e., all elements in the first subset are unique) and it might have one element in common with the second subset.
- The second subset should consist of all same elements (i.e., all elements in the second subset are equal)
Examples:
Input: arr[] = {4, 2, 4, 1, 4, 3, 4}
Output: 3
Explanation: It is possible to construct two subsets of size 3: the first subset is [1, 2, 4] and the second subset is [4, 4, 4]. Note, that there are some other ways to construct two valid teams of size 3.Input: arr[] = {1, 1, 1, 3}
Output: 2
Explanation: It is possible to construct two subsets of size 2: the first subset is [1, 3] and the second subset is [1, 1].
Approach: Implement the idea below to solve the problem:
- Let’s suppose we are able to make two subsets using the given constraints with size x, So, in order to find the maximum size possible, we store the current size x in our answer variable and update low with mid + 1.
- If we were not able to create two subsets using the given constraints with size x, it is sure we would not be able to create two subsets from size x + 1 to n, so we would update high as mid – 1.
- We can get to know if it is possible to form two subsets using the given constraints is possible or not using the map, we can store the frequency of each element in the map and if the frequency of any element is greater than or equal to the size we are checking on and as well as the size of the map-1 should be greater than or equal to the size we are checking on, we would subtract the map size by -1 because it stores the count of distinct elements and 1 element is already used to create the subset which contains all same elements.
Follow the steps mentioned below to implement the idea:
- Initialize low as 0 and high as n/2 initially.
- Calculate mid and check if is it possible to create two subsets using the given constraints
- If possible, update ans to mid (current size) and low to mid +1.
- Else, update high to mid – 1.
- Use a map to store the frequency of each element and to know the possibility of subset formation.
- If the size of the map – 1 is greater than or equal to the size we are checking on and any element is appearing more than or equal to the size we are checking on, then it is always possible to form two subsets so return true else false.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function for checking if is it possible// to create two subsets using the given// constraints with the size midbool 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;}// Function for finding out the// maximum sizeint maximum_size(vector<int>& arr, int n){ // Declare map for storing // the frequency of each element unordered_map<int, int> mpp; for (auto it : arr) { mpp[it]++; } // Range of binary search int low = 0; int high = n / 2; // Store the maximum size int ans = 0; while (low <= high) { // Calculating mid int mid = (low + high) >> 1; // If it possible to create two // subsets, store mid in ans and // update low as mid+1 in order to // find the maximum possible size if (is_possible(mpp, mid)) { ans = mid; low = mid + 1; } // If it is not possible to create // two subsets, it would not be // possible to create subsets from // size mid to n thus, update high // as mid -1 else { high = mid - 1; } } // Return the maximum possible size return ans;}// Driver codeint main(){ vector<int> arr = { 4, 2, 4, 1, 4, 3, 4 }; int n = arr.size(); // Function call cout << maximum_size(arr, n); return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class Main { // Function for checking if is it possible // to create two subsets using the given // constraints with the size mid static boolean is_possible(Map<Integer, Integer> mpp, int mid) { boolean flag1 = false; boolean flag2 = false; boolean flag = false; for (Map.Entry it : mpp.entrySet()) { if ((int)it.getValue() >= mid) { flag1 = true; if ((int)it.getValue() > mid) flag2 = true; } } int size = mpp.size() - 1; if (flag2) size += 1; return flag1 && size >= mid; } // Function for finding out the // maximum size static int maximum_size(int[] arr, int n) { // Declare map for storing // the frequency of each element Map<Integer, Integer> mpp = new HashMap<Integer, Integer>(); for (int it : arr) { if(mpp.containsKey(it)){ mpp.put(it, mpp.get(it)+1); } else{ mpp.put(it,1); } } // Range of binary search int low = 0; int high = n / 2; // Store the maximum size int ans = 0; while (low <= high) { // Calculating mid int mid = (low + high) >> 1; // If it possible to create two // subsets, store mid in ans and // update low as mid+1 in order to // find the maximum possible size if (is_possible(mpp, mid)) { ans = mid; low = mid + 1; } // If it is not possible to create // two subsets, it would not be // possible to create subsets from // size mid to n thus, update high // as mid -1 else { high = mid - 1; } } // Return the maximum possible size return ans; } // Driver code public static void main(String[] args) { int[] arr = { 4, 2, 4, 1, 4, 3, 4 }; int n = arr.length; // Function call System.out.println(maximum_size(arr, n)); }}// This code is contributed by ishankhandelwals. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Function for checking if is it possible to create two // subsets using the given constraints with the size mid static bool is_possible(Dictionary<int, int> mpp, int mid) { bool flag1 = false; bool flag2 = false; foreach(KeyValuePair<int, int> it in mpp) { if (it.Value >= mid) { flag1 = true; if (it.Value > mid) flag2 = true; } } int size = mpp.Count - 1; if (flag2) size += 1; return flag1 && size >= mid; } // Function for finding out the maximum size static int maximum_size(int[] arr, int n) { // Declare map for storing the frequency of each // element Dictionary<int, int> mpp = new Dictionary<int, int>(); foreach(int it in arr) { if (mpp.ContainsKey(it)) { mpp[it] = mpp[it] + 1; } else { mpp.Add(it, 1); } } // Range of binary search int low = 0; int high = n / 2; // Store the maximum size int ans = 0; while (low <= high) { // Calculating mid int mid = (low + high) / 2; // If it possible to create two subsets, store // mid in ans and update low as mid+1 in order // to find the maximum possible size if (is_possible(mpp, mid)) { ans = mid; low = mid + 1; } // If it is not possible to create two subsets, // it would not be possible to create subsets // from size mid to n thus, update high as mid // -1 else { high = mid - 1; } } // Return the maximum possible size return ans; } static public void Main() { // Code int[] arr = { 4, 2, 4, 1, 4, 3, 4 }; int n = arr.Length; // Function call Console.WriteLine(maximum_size(arr, n)); }}// This code is contributed by lokeshmvs21. |
Python3
# Python implementation of the approachfrom collections import defaultdict# Function for checking if it is possible# to create two subsets using the given# constraints with the size middef is_possible(mpp, mid): flag1 = False flag2 = False for key, value in mpp.items(): if value >= mid: flag1 = True if value > mid: flag2 = True size = len(mpp) - 1 if flag2: size += 1 return flag1 and size >= mid# Function for finding out the# maximum sizedef maximum_size(arr): # Dictionary for storing # the frequency of each element mpp = defaultdict(int) for i in arr: mpp[i] += 1 # Range of binary search low = 0 high = len(arr) // 2 # Store the maximum size ans = 0 while low <= high: # Calculating mid mid = (low + high) // 2 # If it is possible to create two # subsets, store mid in ans and # update low as mid + 1 in order to # find the maximum possible size if is_possible(mpp, mid): ans = mid low = mid + 1 # If it is not possible to create # two subsets, it would not be # possible to create subsets from # size mid to n, thus update high # as mid -1 else: high = mid - 1 # Return the maximum possible size return ans# Driver codearr = [4, 2, 4, 1, 4, 3, 4]# Function callprint(maximum_size(arr))#code by ksam24000 |
Javascript
// Function for checking if it is possible// to create two subsets using the given// constraints with the size midfunction is_possible(mpp, mid) { let flag1 = false; let flag2 = false; let flag = false; // Iterate through the unordered_map for (let [key, value] of Object.entries(mpp)) { if (value >= mid) { flag1 = true; if (value > mid) { flag2 = true; } } } let size = Object.keys(mpp).length - 1; if (flag2) { size += 1; } return flag1 && size >= mid;}// Function for finding out the// maximum sizefunction maximum_size(arr, n) { // Declare map for storing // the frequency of each element let mpp = {}; // Count the frequency of each element in arr for (let i = 0; i < n; i++) { mpp[arr[i]] = mpp[arr[i]] ? mpp[arr[i]] + 1 : 1; } // Range of binary search let low = 0; let high = Math.floor(n / 2); // Store the maximum size let ans = 0; while (low <= high) { // Calculating mid let mid = Math.floor((low + high) / 2); // If it possible to create two // subsets, store mid in ans and // update low as mid+1 in order to // find the maximum possible size if (is_possible(mpp, mid)) { ans = mid; low = mid + 1; } // If it is not possible to create // two subsets, it would not be // possible to create subsets from // size mid to n thus, update high // as mid -1 else { high = mid - 1; } } // Return the maximum possible size return ans;}// Driver codelet arr = [4, 2, 4, 1, 4, 3, 4];let n = arr.length;// Function callconsole.log(maximum_size(arr, n)); |
Output
3
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
