Problem Description

You are given an array of integers nums and an integer threshold. Your task is to find the smallest positive integer divisor such that when you divide all elements in the array by this divisor and sum up the results, the total sum is less than or equal to the threshold.

When dividing each element, the result must be rounded up to the nearest integer (ceiling function). For example:

• 7/3 = 3 (since 2.33... rounds up to 3)
• 10/2 = 5 (exactly 5, no rounding needed)

The problem guarantees that there will always be a valid answer.

Example walkthrough: If nums = [1, 2, 5, 9] and threshold = 6:

• If divisor = 5: ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5 ≤ 6 ✓
• If divisor = 4: ceil(1/4) + ceil(2/4) + ceil(5/4) + ceil(9/4) = 1 + 1 + 2 + 3 = 7 > 6 ✗

The goal is to find the smallest divisor value that keeps the sum within the threshold limit.

Intuition

The key observation is that as the divisor increases, the sum of divided results decreases. This creates a monotonic relationship:

• Small divisor → Large sum (each division gives a larger result)
• Large divisor → Small sum (each division gives a smaller result)

For example, with nums = [10]:

• divisor = 1: ceil(10/1) = 10
• divisor = 2: ceil(10/2) = 5
• divisor = 5: ceil(10/5) = 2
• divisor = 10: ceil(10/10) = 1

Since we want the smallest divisor where the sum ≤ threshold, we're looking for a turning point: the first value where the condition becomes true. Everything to the left fails (sum too large), and everything to the right succeeds (sum small enough).

This monotonic property screams binary search! We can search for the smallest valid divisor in the range [1, max(nums)]. Why max(nums) as the upper bound? Because dividing any number by a value greater than or equal to itself always yields 1 (after ceiling), so using any divisor larger than max(nums) won't reduce the sum further.

The binary search checks each candidate divisor by calculating the sum. If the sum is within the threshold, we know this divisor works, but there might be a smaller one, so we search the left half. If the sum exceeds the threshold, we need a larger divisor to reduce the sum, so we search the right half.

Learn more about Binary Search patterns.

Solution Approach

The solution uses binary search to find the smallest valid divisor. Here's how the implementation works:

Binary Search Setup:

• Left boundary: l = 1 (smallest possible divisor)
• Right boundary: r = max(nums) (any divisor larger than this won't reduce the sum further)

The Search Process:

1. Calculate the middle point: mid = (l + r) // 2
2. For the current mid, calculate the sum of all divisions: s = sum(ceil(x/mid) for x in nums)
3. Compare the sum with threshold:
   • If s ≤ threshold: This divisor works, but there might be a smaller one. Update r = mid
   • If s > threshold: We need a larger divisor to reduce the sum. Update l = mid + 1
4. Repeat until l meets r

Calculating Ceiling Division: The code uses a clever trick to calculate ceil(x/v) without using the ceiling function:

• Formula: (x + v - 1) // v
• This works because adding v - 1 to the numerator ensures rounding up for any remainder

The Given Solution's Approach: The provided code uses Python's bisect_left with a custom key function:

def f(v: int) -> bool:
    v += 1
    return sum((x + v - 1) // v for x in nums) <= threshold

return bisect_left(range(max(nums)), True, key=f) + 1

This function f(v) returns True if divisor v+1 produces a sum ≤ threshold. The bisect_left finds the leftmost position where True would fit in the boolean sequence, which corresponds to our smallest valid divisor. The +1 adjustments handle the 0-indexed nature of the range.

Time Complexity: O(n * log(max(nums))) where n is the length of the array Space Complexity: O(1) excluding the input array

Example Walkthrough

Let's walk through a small example to illustrate the binary search approach.

Given: nums = [2, 7, 11] and threshold = 10

Goal: Find the smallest divisor such that ceil(2/d) + ceil(7/d) + ceil(11/d) ≤ 10

Step 1: Initialize binary search boundaries

• Left boundary: l = 1
• Right boundary: r = max(nums) = 11
• Search range: [1, 11]

Step 2: First iteration

• mid = (1 + 11) // 2 = 6
• Calculate sum with divisor 6:
  • ceil(2/6) + ceil(7/6) + ceil(11/6) = 1 + 2 + 2 = 5
• Since 5 ≤ 10, divisor 6 works! But can we find a smaller one?
• Update: r = 6, new range: [1, 6]

Step 3: Second iteration

• mid = (1 + 6) // 2 = 3
• Calculate sum with divisor 3:
  • ceil(2/3) + ceil(7/3) + ceil(11/3) = 1 + 3 + 4 = 8
• Since 8 ≤ 10, divisor 3 works! Continue searching for smaller.
• Update: r = 3, new range: [1, 3]

Step 4: Third iteration

• mid = (1 + 3) // 2 = 2
• Calculate sum with divisor 2:
  • ceil(2/2) + ceil(7/2) + ceil(11/2) = 1 + 4 + 6 = 11
• Since 11 > 10, divisor 2 is too small (sum exceeds threshold).
• Update: l = 3, new range: [3, 3]

Step 5: Convergence

• l = r = 3, so we've found our answer!

Answer: The smallest divisor is 3, which gives us a sum of 8 ≤ 10.

Verification of neighboring values:

• Divisor 2: sum = 11 (too large, exceeds threshold)
• Divisor 3: sum = 8 (valid, within threshold) ✓
• Divisor 4: sum = 6 (valid, but not the smallest)

The binary search efficiently found the turning point where the divisor becomes just large enough to keep the sum within the threshold.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the array nums and M is the maximum value in the array nums. This is because:

• The binary search using bisect_left performs O(log M) iterations over the range [0, max(nums)).
• In each iteration, the function f is called, which computes the sum of ceiling divisions for all elements in nums, taking O(n) time.
• Therefore, the total time complexity is O(n × log M).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables like v and the sum calculation, regardless of the input size. The range(max(nums)) in bisect_left is treated as a virtual range and doesn't create an actual list in memory.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error with Index vs. Divisor Value

The most common mistake is confusion between the index used in bisect_left and the actual divisor value. The code searches through range(max(nums)) which gives indices [0, 1, 2, ..., max(nums)-1], but the actual divisors we want to test are [1, 2, 3, ..., max(nums)].

Wrong approach:

def can_meet_threshold(divisor: int) -> bool:
    # ERROR: Using divisor directly without adding 1
    total_sum = sum((num + divisor - 1) // divisor for num in nums)
    return total_sum <= threshold

# This would cause division by zero when divisor=0

Correct approach:

def can_meet_threshold(divisor: int) -> bool:
    actual_divisor = divisor + 1  # Convert index to actual divisor
    total_sum = sum((num + actual_divisor - 1) // actual_divisor for num in nums)
    return total_sum <= threshold

2. Incorrect Ceiling Division Formula

Many developers try to use floating-point division with math.ceil, which can lead to precision issues and is less efficient.

Problematic approach:

import math
total_sum = sum(math.ceil(num / divisor) for num in nums)
# Can have floating-point precision issues

Better approach:

# Integer-only arithmetic: ceil(x/d) = (x + d - 1) // d
total_sum = sum((num + divisor - 1) // divisor for num in nums)

3. Wrong Binary Search Boundaries

Setting the right boundary incorrectly can miss valid solutions or cause unnecessary iterations.

Wrong:

# Setting right boundary too small
bisect_left(range(min(nums)), True, key=can_meet_threshold)
# May not find valid divisors for larger numbers

# Setting right boundary unnecessarily large
bisect_left(range(sum(nums)), True, key=can_meet_threshold)
# Wastes time checking divisors that can't improve the answer

Correct:

# Right boundary should be max(nums) since any divisor larger 
# than the maximum element won't reduce the sum further
bisect_left(range(max(nums)), True, key=can_meet_threshold)

4. Misunderstanding bisect_left Return Value

bisect_left returns the leftmost position where the condition becomes True. Forgetting to add 1 at the end gives an off-by-one error.

Wrong:

return bisect_left(range(max(nums)), True, key=can_meet_threshold)
# Returns index, not the actual divisor value

Correct:

return bisect_left(range(max(nums)), True, key=can_meet_threshold) + 1
# Converts 0-indexed position to 1-indexed divisor

Alternative Clear Solution

To avoid these pitfalls, consider a more explicit binary search implementation:

def smallestDivisor(self, nums: List[int], threshold: int) -> int:
    left, right = 1, max(nums)
  
    while left < right:
        mid = (left + right) // 2
        total = sum((num + mid - 1) // mid for num in nums)
      
        if total <= threshold:
            right = mid  # Try smaller divisor
        else:
            left = mid + 1  # Need larger divisor
  
    return left

This approach directly works with divisor values rather than indices, making the logic clearer and reducing the chance of off-by-one errors.