Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in plain language

Given a list of positive integers, choose one positive integer divisor. Divide every number by it, round each quotient up, and add the rounded values. The goal is to find the smallest divisor that makes this sum no greater than threshold.

For example, with nums = [1, 2, 5, 9] and divisor 5, the rounded quotients are [1, 1, 1, 2], whose sum is 5. A divisor of 4 produces [1, 1, 2, 3], whose sum is 7. If the threshold is 6, divisor 5 works and divisor 4 does not, so 5 is the answer.

Trying every divisor would be too slow when array values are large. The useful structure is that the candidate divisors are ordered by feasibility.

Deriving the optimal solution

For a fixed positive number value, its contribution is:

ceil(value / divisor) = (value + divisor - 1) // divisor

As the divisor increases, that contribution can only stay the same or decrease. Therefore, the total rounded sum can only stay the same or decrease too. Candidate divisors consequently form two regions:

too small, too small, ..., too small, works, works, ..., works

The answer is the first divisor in the works region. That is exactly a lower-bound binary search.

Choosing the search boundaries

The smallest possible divisor is 1. The largest necessary divisor is max(nums): at that value, every positive array element contributes exactly 1, so the total is len(nums). The problem guarantees threshold >= len(nums), which makes this upper bound feasible.

Keep an inclusive search interval [left, right] that contains the smallest feasible divisor. For its midpoint:

  • If the rounded sum is at most threshold, the midpoint works, but a smaller divisor might also work, so keep it by setting right = midpoint.
  • If the sum is too large, the midpoint and every smaller divisor fail, so set left = midpoint + 1.

When the boundaries meet, they identify the smallest feasible divisor.

For efficiency and numerical safety, compute each ceiling with integer arithmetic instead of floating point. The feasibility check can also stop as soon as its running sum exceeds the threshold, because all remaining contributions are positive and cannot restore feasibility.

If n is the array length and M = max(nums), binary search tests O(log M) divisors and each test scans at most n values. The total complexity is O(n log M) time and O(1) extra space.

Python solution

from collections.abc import Sequence


class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        """Return the smallest divisor whose rounded-up sum fits threshold."""
        self._validate_inputs(nums, threshold)

        smallest_candidate = 1
        largest_candidate = max(nums)

        # Find the first divisor for which the monotone feasibility test is true.
        while smallest_candidate < largest_candidate:
            candidate = smallest_candidate + (
                largest_candidate - smallest_candidate
            ) // 2

            if self._is_within_threshold(nums, candidate, threshold):
                largest_candidate = candidate
            else:
                smallest_candidate = candidate + 1

        return smallest_candidate

    @staticmethod
    def _is_within_threshold(
        nums: Sequence[int],
        divisor: int,
        threshold: int,
    ) -> bool:
        """Check feasibility without using floating-point arithmetic."""
        rounded_sum = 0

        for value in nums:
            rounded_sum += (value + divisor - 1) // divisor

            # Every remaining value adds at least one, so an exceeded
            # threshold can never become feasible later in the scan.
            if rounded_sum > threshold:
                return False

        return True

    @staticmethod
    def _validate_inputs(nums: Sequence[int], threshold: int) -> None:
        """Reject inputs outside the assumptions that make an answer exist."""
        if not nums:
            raise ValueError("nums must contain at least one value")
        if any(value <= 0 for value in nums):
            raise ValueError("every value in nums must be positive")
        if threshold < len(nums):
            raise ValueError("threshold must be at least the length of nums")

Interview follow-ups

Why is binary search valid even though the input array is not sorted?

The search is not over array positions. It is over the numeric answer space from 1 through max(nums). What matters is that the predicate “this divisor produces a sum no greater than the threshold” is monotone: once it becomes true, it stays true for every larger divisor. Binary search needs an ordered monotone decision space, not necessarily a sorted input collection.

Could the upper bound be tighter than max(nums)?

Yes. Since every element contributes at least 1, there are threshold - len(nums) units of contribution available beyond that unavoidable baseline. A tighter bound can sometimes be derived from the values and this budget, but it complicates the reasoning and does not improve the asymptotic complexity.

Using max(nums) is simple, always feasible under the stated constraints, and at most 10^6, so binary search needs only about twenty iterations. In an interview, that clean invariant is usually more valuable than shaving a few iterations from an already logarithmic search.

How would the solution change if no feasible divisor were guaranteed?

First define whether arbitrarily large divisors are allowed. With positive inputs, every element approaches a rounded contribution of 1, so no divisor can make the sum smaller than len(nums). If threshold < len(nums), return a sentinel such as -1 or raise an exception immediately.

If the candidate divisor has an external maximum, evaluate that maximum before searching. A false result means the feasible region is empty. Otherwise, the same lower-bound binary search applies inside the allowed interval. This explicit precheck protects the invariant that the right boundary is feasible.

What if the interviewer asks for the largest divisor whose sum is at least the threshold?

The rounded sum is still monotone nonincreasing, but the desired boundary changes. The predicate “sum is at least the threshold” is true for smaller divisors and false for larger ones, so search for the last true candidate rather than the first true candidate. The midpoint bias and boundary updates must be adjusted to ensure the loop always progresses.

The feasibility calculation remains O(n), and the overall complexity remains O(n log M). The important interview skill is to state which boundary is being found before writing the binary-search template.

How would repeated threshold queries on the same array change the design?

For a modest number of queries, run the same O(n log M) search independently; it is simple and uses constant auxiliary space. Cache the rounded sum for each divisor that gets tested, because different queries may probe the same candidates. A cache trades up to O(M) space in the worst case for avoiding repeated scans.

If there are extremely many queries and M is manageable, precompute the rounded sum for every divisor, producing a monotone lookup table in O(nM) time and O(M) space, then binary-search it per query in O(log M). That preprocessing is only worthwhile when the query volume justifies its much larger upfront cost.

Why avoid math.ceil(value / divisor)?

The expression first performs floating-point division. It is safe under this problem’s small constraints, but large integers in a generalized version may lose precision when converted to floating point. The integer identity (value + divisor - 1) // divisor is exact for positive integers and makes the intended rounding explicit.

If values might be near a fixed-width integer limit in another language, use 1 + (value - 1) // divisor instead. It represents the same ceiling while avoiding possible overflow in value + divisor - 1.

Takeaway

When a problem asks for the smallest numeric value satisfying a condition, test whether feasibility changes monotonically as that value grows. Here, larger divisors never increase the rounded sum, turning a large answer range into a first-true binary search. Careful boundaries, exact ceiling arithmetic, and an early-exit feasibility check make the solution both efficient and easy to justify.