Question

2910. Minimum Number of Groups to Create a Valid Assignment

中文文档

Description

You are given a collection of numbered balls and instructed to sort them into boxes for a nearly balanced distribution. There are two rules you must follow:

• Balls with the same box must have the same value. But, if you have more than one ball with the same number, you can put them in different boxes.
• The biggest box can only have one more ball than the smallest box.

​Return the _fewest number of boxes_ to sort these balls following these rules.

 

Example 1:

Input: balls = [3,2,3,2,3]

Output: 2

Explanation:

We can sort balls into boxes as follows:

• [3,3,3]
• [2,2]

The size difference between the two boxes doesn't exceed one.

Example 2:

Input: balls = [10,10,10,3,1,1]

Output: 4

Explanation:

We can sort balls into boxes as follows:

• [10]
• [10,10]
• [3]
• [1,1]

You can't use fewer than four boxes while still following the rules. For example, putting all three balls numbered 10 in one box would break the rule about the maximum size difference between boxes.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Solutions

Solution 1: Hash Table + Enumeration

We use a hash table $cnt$ to count the number of occurrences of each number in the array $nums$. Let $k$ be the minimum value of the number of occurrences, and then we can enumerate the size of the groups in the range $[k,..1]$. Since the difference in size between each group is not more than $1$, the group size can be either $k$ or $k+1$.

For the current group size $k$ being enumerated, we traverse each occurrence $v$ in the hash table. If $\lfloor \frac{v}{k} \rfloor < v \bmod k$, it means that we cannot divide the occurrence $v$ into $k$ or $k+1$ groups with the same value, so we can skip this group size $k$ directly. Otherwise, it means that we can form groups, and we only need to form as many groups of size $k+1$ as possible to ensure the minimum number of groups. Therefore, we can divide $v$ numbers into $\lceil \frac{v}{k+1} \rceil$ groups and add them to the current enumerated answer. Since we enumerate $k$ from large to small, as long as we find a valid grouping scheme, it must be optimal.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def minGroupsForValidAssignment(self, nums: List[int]) -> int:
    cnt = Counter(nums)
    for k in range(min(cnt.values()), 0, -1):
      ans = 0
      for v in cnt.values():
        if v // k < v % k:
          ans = 0
          break
        ans += (v + k) // (k + 1)
      if ans:
        return ans

class Solution {
  public int minGroupsForValidAssignment(int[] nums) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) {
      cnt.merge(x, 1, Integer::sum);
    }
    int k = nums.length;
    for (int v : cnt.values()) {
      k = Math.min(k, v);
    }
    for (;; --k) {
      int ans = 0;
      for (int v : cnt.values()) {
        if (v / k < v % k) {
          ans = 0;
          break;
        }
        ans += (v + k) / (k + 1);
      }
      if (ans > 0) {
        return ans;
      }
    }
  }
}

class Solution {
public:
  int minGroupsForValidAssignment(vector<int>& nums) {
    unordered_map<int, int> cnt;
    for (int x : nums) {
      cnt[x]++;
    }
    int k = 1e9;
    for (auto& [_, v] : cnt) {
      ans = min(ans, v);
    }
    for (;; --k) {
      int ans = 0;
      for (auto& [_, v] : cnt) {
        if (v / k < v % k) {
          ans = 0;
          break;
        }
        ans += (v + k) / (k + 1);
      }
      if (ans) {
        return ans;
      }
    }
  }
};

func minGroupsForValidAssignment(nums []int) int {
  cnt := map[int]int{}
  for _, x := range nums {
    cnt[x]++
  }
  k := len(nums)
  for _, v := range cnt {
    k = min(k, v)
  }
  for ; ; k-- {
    ans := 0
    for _, v := range cnt {
      if v/k < v%k {
        ans = 0
        break
      }
      ans += (v + k) / (k + 1)
    }
    if ans > 0 {
      return ans
    }
  }
}

function minGroupsForValidAssignment(nums: number[]): number {
  const cnt: Map<number, number> = new Map();
  for (const x of nums) {
    cnt.set(x, (cnt.get(x) || 0) + 1);
  }
  for (let k = Math.min(...cnt.values()); ; --k) {
    let ans = 0;
    for (const [_, v] of cnt) {
      if (((v / k) | 0) < v % k) {
        ans = 0;
        break;
      }
      ans += Math.ceil(v / (k + 1));
    }
    if (ans) {
      return ans;
    }
  }
}

use std::collections::HashMap;

impl Solution {
  pub fn min_groups_for_valid_assignment(nums: Vec<i32>) -> i32 {
    let mut cnt: HashMap<i32, i32> = HashMap::new();

    for x in nums.iter() {
      let count = cnt.entry(*x).or_insert(0);
      *count += 1;
    }

    let mut k = i32::MAX;

    for &v in cnt.values() {
      k = k.min(v);
    }

    for k in (1..=k).rev() {
      let mut ans = 0;

      for &v in cnt.values() {
        if v / k < v % k {
          ans = 0;
          break;
        }

        ans += (v + k) / (k + 1);
      }

      if ans > 0 {
        return ans;
      }
    }

    0
  }
}