3166. Minimum Number of Groups to Create a Valid Assignment
My accepted Python solution to LeetCode problem 3166, Minimum Number of Groups to Create a Valid Assignment, running in 63ms.
- Difficulty: Medium
- Python
- Runtime 63ms
- Memory 38.2MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 63ms, memory 38.2MB, accepted 2025-12-30.
class Solution:
def minGroupsForValidAssignment(self, balls: List[int]) -> int:
from collections import Counter
count = Counter(balls)
freq = list(count.values())
min_freq = min(freq)
# Try group sizes from min_freq down to 1
for group_size in range(min_freq, 0, -1):
total_groups = 0
valid = True
for f in freq:
# Each frequency f needs to be split into groups of size group_size or group_size+1
# We need: a * group_size + b * (group_size + 1) = f
# where a >= 0 and b >= 0
# Rearranging: a * group_size + b * group_size + b = f
# (a + b) * group_size + b = f
# Let total = a + b (total number of groups for this frequency)
# total * group_size + b = f, where 0 <= b <= total
# b = f - total * group_size, and 0 <= b <= total
# So: 0 <= f - total * group_size <= total
# f - total * group_size >= 0 => total <= f / group_size
# f - total * group_size <= total => f <= total * (group_size + 1)
# => total >= f / (group_size + 1)
# So: ceil(f / (group_size + 1)) <= total <= floor(f / group_size)
min_groups = (f + group_size) // (group_size + 1) # ceil(f / (group_size + 1))
max_groups = f // group_size
if min_groups > max_groups:
valid = False
break
total_groups += min_groups
if valid:
return total_groups
return len(balls) # Worst case: each ball in its own group