Skip to content

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<int>& nums) {
    unordered_map<int, int> 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<int, int>& 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<Integer, Integer> 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<Integer, Integer> 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