Domain 2MediumMEDIUM

Find the Smallest Divisor Given a Threshold

Uses binary search on the answer space [1, max(nums)] to find the smallest divisor where ceiling sum <= threshold.

Domain: medium•Updated: 2026-09-13
#binary-search#math

Problem Breakdown

We are given an array of positive integers nums and a target limit called threshold. We need to determine the minimum integer divisor such that when every element in nums is divided by this divisor (rounding up any fractional part), the total sum does not exceed threshold.

Key Inputs:

  • nums: List of integers (1≤nums[i]≤1061 \le nums[i] \le 10^6).
  • threshold: Integer limit for the calculated sum.

Implicit Constraints & Edge Cases:

  • Monotonicity: As we increase the divisor, each term ⌈ni/d⌉\lceil n_i / d \rceil either decreases or stays constant. Consequently, the total sum is a non-increasing function of the divisor. This monotonic property allows us to use Binary Search on Answer rather than iterating through divisors directly.
  • Search Space: The smallest possible divisor is 1 (worst case for sum). The largest necessary divisor we need to check is max(nums). If a divisor exceeds max(nums), every element becomes 1, and the sum equals len(nums). Since constraints guarantee nums.length <= threshold, this state is always valid.
  • Rounding: “Nearest integer greater than or equal” implies ceiling division (⌈x/y⌉\lceil x/y \rceil). In Python, (x + y - 1) // y achieves this efficiently without floating-point errors.

Intuition

A naive approach would be to iterate through every possible divisor starting from 1 up to the maximum element in nums. For each candidate divisor, we calculate the sum of ceilings and check against the threshold. This brute force has a time complexity proportional to O(N⋅M)O(N \cdot M) where NN is array length and MM is max value (≈106\approx 10^6). Given constraints up to 5×1045 \times 10^4, this would likely Time Out (TLE) or be inefficient.

However, observe the relationship between divisor and sum:

  • If divisor = 1, sum is maximum possible (≈N⋅Mavg\approx N \cdot M_{avg}).
  • As divisor increases, sum decreases.
  • We want the smallest divisor where sum ≤\le threshold.

Since the function “Sum vs Divisor” is monotonic (decreasing), we can apply Binary Search on the answer space [1,max⁡(nums)][1, \max(nums)]. This reduces complexity from linear scan of values to logarithmic steps over values (O(Nlog⁡M)O(N \log M)).

Approach

  1. Initialize Bounds: Set left = 1 and right = max(nums). We will search for a valid divisor in this range.
  2. Binary Search Loop: While left <= right:
    • Calculate mid = (left + right) // 2.
    • Compute the total sum using integer ceiling division: (num + mid - 1) // mid for each element.
    • Compare computed sum with threshold.
      • If sum <= threshold: This divisor works, but we might find a smaller one that also works. Store mid as potential answer and try left half (right = mid - 1).
      • If sum > threshold: Divisor is too small (resulting in sum being too large). We need to increase the divisor (left = mid + 1).
  3. Return: The smallest valid divisor found during the search process.

Complexity Analysis

  • Time Complexity: O(Nlog⁡M)O(N \log M), where NN is len(nums) and MM is max(nums). We perform binary search over the range of values (roughly log⁡(106)≈20\log(10^6) \approx 20 iterations). Inside each iteration, we iterate through the array (O(N)O(N)) to compute the sum.
  • Space Complexity: O(1)O(1) auxiliary space. We only use a few variables for pointers and accumulation; no recursion or large data structures are needed.

Solution

def smallestDivisor(nums: list[int], threshold: int) -> int:
    # Binary search range: [1, max(nums)]
    left = 1
    right = max(nums) if nums else 0
    
    ans = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Calculate sum of ceilings for current divisor 'mid'
        total_sum = 0
        for num in nums:
            # Integer ceiling division equivalent to math.ceil(num / mid)
            total_sum += (num + mid - 1) // mid
            
        if total_sum <= threshold:
            ans = mid      # Found a valid divisor, try smaller ones
            right = mid - 1
        else:
            left = mid + 1
    
    return ans

# Example usage for verification purposes only (remove in submission)
if __name__ == "__main__":
    print(smallestDivisor([1,2,5,9], 6))      # Expected: 5
    print(smallestDivisor([44,22,33,11,1], 5))# Expected: 44

Edge Cases Handled

  • Large Values: Inputs up to 10610^6 are handled naturally by Python’s arbitrary precision integers and the logarithmic search depth.
  • Threshold Tightness: If threshold is exactly equal to len(nums), the binary search will converge on a divisor ≥max⁡(nums)\ge \max(nums), ensuring every term rounds down to 1. The logic holds because (num + mid - 1) // mid becomes 1 when mid >= num.
  • Empty Array: While constraints say N≥1N \ge 1, the code initializes right = max(nums) which handles empty lists safely (though not expected per constraints).
  • Divisor Calculation: The formula (num + mid - 1) // mid correctly implements ceiling division for positive integers without floating-point overhead.