# 2910. Minimum Number of Groups to Create a Valid Assignment¶

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public: int minGroupsForValidAssignment(vector& nums) { unordered_map count; int minFreq = nums.size(); for (const int num : nums) ++count[num]; for (const auto& [_, freq] : count) minFreq = min(minFreq, freq); for (int groupSize = minFreq; groupSize >= 1; --groupSize) { const int numGroups = getNumGroups(count, groupSize); if (numGroups > 0) return numGroups; } throw; } private: // Returns the number of groups if each group's size is groupSize or // groupSize + 1. int getNumGroups(unordered_map& count, int groupSize) { int numGroups = 0; for (const auto& [_, freq] : count) { const int a = freq / (groupSize + 1); const int b = freq % (groupSize + 1); if (b == 0) { numGroups += a; } else if (groupSize - b <= a) { // Assign 1 number from groupSize - b out of a groups to this group, // so we'll have a - (groupSize - b) groups of size groupSize + 1 // and groupSize - b + 1 groups of size groupSize. In total, we have // a + 1 groups. numGroups += a + 1; } else { return 0; } } return numGroups; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public int minGroupsForValidAssignment(int[] nums) { Map count = new HashMap<>(); int minFreq = nums.length; for (final int num : nums) count.merge(num, 1, Integer::sum); for (final int freq : count.values()) minFreq = Math.min(minFreq, freq); for (int groupSize = minFreq; groupSize >= 1; --groupSize) { final int numGroups = getNumGroups(count, groupSize); if (numGroups > 0) return numGroups; } throw new IllegalArgumentException(); } // Returns the number of groups if each group's size is groupSize or // groupSize + 1. private int getNumGroups(Map count, int groupSize) { int numGroups = 0; for (final int freq : count.values()) { final int a = freq / (groupSize + 1); final int b = freq % (groupSize + 1); if (b == 0) { numGroups += a; } else if (groupSize - b <= a) { // Assign 1 number from groupSize - b out of a groups to this group, // so we'll have a - (groupSize - b) groups of size groupSize + 1 // and groupSize - b + 1 groups of size groupSize. In total, we have // a + 1 groups. numGroups += a + 1; } else { return 0; } } return numGroups; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution: def minGroupsForValidAssignment(self, nums: List[int]) -> int: count = collections.Counter(nums) minFreq = min(count.values()) for groupSize in range(minFreq, 0, -1): numGroups = self.getNumGroups(count, groupSize) if numGroups > 0: return numGroups raise ValueError("Invalid argument") def getNumGroups(self, count: Dict[int, int], groupSize: int) -> int: """Returns the number of groups if each group's size is groupSize or groupSize + 1.""" numGroups = 0 for freq in count.values(): a = freq // (groupSize + 1) b = freq % (groupSize + 1) if b == 0: # Assign 1 number from groupSize - b out of a groups to this group, # so we'll have a - (groupSize - b) groups of size groupSize + 1 # and groupSize - b + 1 groups of size groupSize. In total, we have # a + 1 groups. numGroups += a elif groupSize - b <= a: numGroups += a + 1 else: return 0 return numGroups