Find the Smallest Divisor Given a Threshold

Find the Smallest Divisor Given a Threshold is LeetCode 1283, and it is one of those problems that looks like it needs some clever math trick but actually falls right into the binary search on answer pattern. Once you see the connection, the solution is short and clean.

If you have worked through Koko Eating Bananas or Capacity to Ship Packages Within D Days, you already know the template. This problem is the same skeleton with a different feasibility check.

The problem

You are given an array of integers nums and an integer threshold. Choose a positive integer divisor d. For each element in the array, divide it by d and round up (ceiling division). Sum all the results. Return the smallest divisor such that this sum is less than or equal to threshold.

It is guaranteed that a valid divisor exists (the problem states threshold >= len(nums), so d = max(nums) always works since every ceiling becomes 1).

Example: nums = [1, 2, 5, 9], threshold = 6.

At divisor d = 5, the sum is ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5. That is within the threshold. Anything smaller, like d = 4, gives ceil(1/4) + ceil(2/4) + ceil(5/4) + ceil(9/4) = 1 + 1 + 2 + 3 = 7, which exceeds the threshold. So the answer is 5.

Why binary search works here

Think about what happens as you increase the divisor. With d = 1, every element stays the same and the sum is as large as possible. As d grows, each ceil(num/d) either stays the same or gets smaller. The sum never increases when you increase the divisor.

That monotonic relationship is the key. The answer space [1, max(nums)] splits into two regions:

• Infeasible: divisors 1 through answer - 1 produce a sum that exceeds the threshold
• Feasible: divisors answer through max(nums) produce a sum within the threshold

When you have a monotonic split like this, binary search finds the boundary in O(log n) time.

The feasibility check

Before writing the binary search, define the test: "Does divisor d produce a sum that is at most threshold?"

def is_feasible(nums, d, threshold):
    total = 0
    for num in nums:
        total += (num + d - 1) // d
    return total <= threshold

For each element, (num + d - 1) // d computes ceil(num / d) using integer arithmetic. Sum them all up. If the total is at most threshold, the divisor works.

Visual walkthrough

Let's trace the binary search for nums = [1, 2, 5, 9], threshold = 6. The search range for the divisor is [1, 9].

Four steps instead of checking all nine candidates. For larger ranges (say, max element up to 10^6), binary search still takes at most about 20 steps. That is the power of O(log n).

The code

Here is the complete Python solution for LeetCode 1283:

import math

def smallest_divisor(nums, threshold):
    lo, hi = 1, max(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        total = sum(math.ceil(num / mid) for num in nums)

        if total <= threshold:
            hi = mid
        else:
            lo = mid + 1

    return lo

Let's walk through the important decisions.

lo = 1, hi = max(nums). The smallest possible divisor is 1. The largest useful divisor is max(nums), because any divisor bigger than that makes every ceiling equal to 1, which is the same result as d = max(nums).

while lo < hi, not while lo <= hi. We are narrowing to a single answer. When lo == hi, that is the answer.

if total <= threshold: hi = mid. If the current divisor works, it might be the answer, or a smaller divisor might also work. Keep mid in the range and search left.

else: lo = mid + 1. If the current divisor does not work (sum too large), we need a bigger divisor. Move lo past mid.

Return lo. When the loop ends, lo == hi and that is the minimum valid divisor.

You can also use the integer ceiling trick (num + mid - 1) // mid instead of math.ceil(num / mid) to avoid floating-point math entirely:

def smallest_divisor(nums, threshold):
    lo, hi = 1, max(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        total = sum((num + mid - 1) // mid for num in nums)

        if total <= threshold:
            hi = mid
        else:
            lo = mid + 1

    return lo

Both versions are correct. The integer version avoids any floating-point precision concerns and is commonly preferred in competitive programming.

Complexity analysis

For the constraints in LeetCode 1283 (nums[i] up to 10^6, n up to 5 * 10^4), this is about 20 * 50,000 = 1,000,000 operations. Very fast.

The building blocks

This problem is built on two core building blocks.

Binary search on the answer. Instead of searching a sorted array for a target, you search a range of candidate answers for the smallest one that satisfies a condition. The skeleton is always:

while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

If you can write this template from memory, the only thing that changes between problems is the is_feasible function.

Ceiling division. The expression math.ceil(a / b) can also be written as (a + b - 1) // b using only integer math. This shows up constantly in binary-search-on-answer problems. In Koko Eating Bananas, you compute ceil(piles[i] / k). In Capacity to Ship Packages, you compare accumulated weight to capacity. Here, you compute ceil(nums[i] / d). The pattern is always "divide, round up, sum, compare to a limit."

Edge cases to watch for

• All elements equal: nums = [5, 5, 5], threshold = 3. You need each ceiling to be 1, so d = 5.
• Threshold equals n: threshold = len(nums). Every ceiling must be 1, so d = max(nums).
• Single element: nums = [100], threshold = 1. You need ceil(100/d) = 1, so d = 100.
• Large threshold: If threshold is very large, even d = 1 works (sum equals sum(nums)).
• Elements equal to 1: nums = [1, 1, 1], threshold = 3. Any divisor works, answer is 1.

From understanding to recall

The logic here is clean. Binary search the range of divisors, check feasibility at each midpoint, narrow down to the smallest valid divisor. You probably get it right now.

But try writing it from scratch in a timed interview next month. Was it lo < hi or lo <= hi? Do you set hi = mid or hi = mid - 1? What are the initial bounds? These details slip under pressure if you have not practiced them recently.

Spaced repetition is designed for exactly this. You write the solution today, then again tomorrow, then in three days. After a few rounds, the while lo < hi / hi = mid pattern is automatic. You do not have to rederive it, you just write it.

LeetCode 1283 is a strong SRS candidate because the code is short (about 8 lines), the pattern transfers directly to at least five other problems, and the boundary conditions trip people up when they have not drilled them.

Related posts

• Koko Eating Bananas: Binary Search on the Answer -- The classic search-on-answer problem. Same template, different feasibility check.
• Capacity to Ship Packages Within D Days -- Another binary-search-on-answer variant where you search over ship capacity instead of divisor size.
• Binary Search: More Than Finding a Number -- The full binary search pattern guide, including the search-on-answer variant used in this problem.