We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Groups to Create a Valid Assignment

Number: 3166

Difficulty: Medium

Paid? No

Companies: BNY Mellon

Problem Description

We are given an array of integers (called “balls”) where each integer represents the number on the ball. We must partition (or “assign”) these balls into several boxes subject to two rules:

  1. All balls within a given box must have the same number (though the same number may appear in different boxes).
  2. If we look at the sizes (i.e. counts) of balls in all boxes, the difference between the largest and smallest box count must be at most one.

Return the fewest number of boxes (groups) we need to assign all the balls following these rules.

Key Insights

  • The boxes must be “nearly balanced” – every box’s size is either m or m+1 for some integer m.
  • We are allowed to split the balls of the same number across boxes.
  • For each ball type with frequency f, if we decide to use t boxes for that number then the t boxes will each receive either m or m+1 balls; hence, the total count f must lie between tm and t(m+1).
  • Globally if we use k boxes, then there exist an integer m and an “extra‐box count” r such that: • n = m*k + r (where n is the total number of balls, and 0 ≤ r < k) • All boxes have size m or m+1.
  • For each distinct ball number with frequency f, if we “split” its f balls into t boxes then t must lie between: • Lower bound: ceil(f/(m+1)) (if every box for that type gets the larger quantity) • Upper bound: floor(f/m) (if every box for that type gets the smaller quantity)
  • In addition, when summing over all ball types, the total number of boxes used (i.e. the sum across the types of the t values) must equal k. Also, the “extra” balls summed over the ball types must add up to r.
  • A neat approach is to “guess” the smaller box size L (which plays the role of m). Notice that L must be at most the minimum frequency among the ball types (otherwise a ball type with less than L balls cannot fill even a single box of size L).
  • For a chosen L the total number of boxes k must satisfy two conditions: • Based on the overall total n, since boxes are of size L or L+1, we have: ceil(n/(L+1)) ≤ k ≤ floor(n/L). • For each ball type with frequency f, if we must use between ceil(f/(L+1)) and floor(f/L) boxes then overall: sum(ceil(f/(L+1))) ≤ k ≤ sum(f // L).
  • We then try each candidate L (from 1 to the minimum frequency) and, if the two ranges intersect, choose the smallest possible k from the intersection.
  • This greedy “range‐intersection” approach finds the minimal number of boxes needed.

Space and Time Complexity

Time Complexity: O(D) where D is the number of distinct ball numbers (D ≤ length of the input, up to 10^5).
Space Complexity: O(D) for storing the frequency counts.

Solution

We solve the problem by iterating over possible candidate values for the smaller box size L (which must lie between 1 and the minimum frequency among the ball types). For a given L, the total number of boxes k must satisfy two sets of constraints:

  1. From the total number of balls n: • k must be at least ceil(n/(L+1)) and at most floor(n/L).

  2. From the distribution over each ball type: • For a ball type with frequency f, using t boxes to store its f balls needs to satisfy: ceil(f/(L+1)) ≤ t ≤ floor(f/L) • Therefore, when summing over all ball types, k must lie between: total_lower = sum(ceil(f/(L+1))) and total_upper = sum(f // L)

If there is an intersection between the range [ceil(n/(L+1)), floor(n/L)] and [total_lower, total_upper] then a valid assignment with k boxes is possible. Among all candidate L with a nonempty intersection, we pick the smallest k available.

We then implement this logic and provide commented solutions in Python, JavaScript, C++ and Java.

Code Solutions

# Python solution
import math
from collections import Counter

def minBoxes(balls):
    n = len(balls)
    freq = Counter(balls)
    # The candidate L (the smaller box size) cannot exceed the minimum frequency.
    min_freq = min(freq.values())
    ans = float('inf')
    
    # Iterate L from 1 up to min_freq
    for L in range(1, min_freq + 1):
        # Based on overall total balls, valid k must satisfy:
        k_lower_global = math.ceil(n / (L + 1))
        k_upper_global = n // L  # floor(n/L)
        
        # Calculate the total lower and upper bounds for boxes required from each ball type.
        total_lower = 0
        total_upper = 0
        valid = True
        for f in freq.values():
            # If a ball type does not even have L balls, then L is impossible.
            if f < L:
                valid = False
                break
            # For this ball type, the minimal boxes needed is if every box gets (L+1) balls.
            req_low = math.ceil(f / (L + 1))
            # Maximum boxes allowed is if every box gets L balls.
            req_high = f // L
            total_lower += req_low
            total_upper += req_high
        
        # Skip candidate L if any ball type is invalid.
        if not valid:
            continue
        
        # Overall k must lie in intersection between global range and per-type range.
        k_lower = max(k_lower_global, total_lower)
        k_upper = min(k_upper_global, total_upper)
        
        if k_lower <= k_upper:
            # A valid k can be chosen; choose the smallest candidate in the intersection.
            ans = min(ans, k_lower)
    
    return ans if ans != float('inf') else -1  # According to constraints, answer always exists.

# Example runs:
print(minBoxes([3,2,3,2,3]))  # Expected output: 2
print(minBoxes([10,10,10,3,1,1]))  # Expected output: 4
← Back to All Questions