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 <= 1051 <= nums[i] <= 109
Solution
Python3
class Solution:
def minGroupsForValidAssignment(self, nums: List[int]) -> int:
N = len(nums)
counter = Counter(nums)
minCount = min(counter.values())
def count(size):
res = 0
for v in counter.values():
d, rem = divmod(v, size + 1)
if rem == 0:
res += d
# So far we have divided things into numGroups + 1 groups
# where the first numGroups have size + 1 elements
# and the last group has has remaining = {1 ... size} elements.
#
# In order to make this grouping valid, each group out of numGroups
# can potentially give 1 element to the last group.
#
# The idea is that a subset of those groups should be able to give 1 element
# each to the last group so that the last group also has size elements.
#
# In other words, in order for the last group to have size elements,
# size - remaining groups have to contribute 1 element each.
#
# So there must be at least size - remaining groups of size + 1 elements.
elif d >= (size - rem):
res += d + 1
else:
return -1
return res
for size in range(minCount, 0, -1):
cnt = count(size)
if cnt != -1:
return cnt
return -1