Problem Statement

Smallest Divisor Given Threshold

You have a list of numbers and a budget called the threshold. You pick one divisor, which is a number you divide every item by. For each item you divide, then round up to the next whole number. Rounding up is called the ceiling, so ceil(9/5) is 2, not 1, because 9/5 is 1.8 and we always bump it up. Add all those rounded results together to get a sum. Your job is to find the smallest divisor that keeps this sum at or below the threshold. The key fact: when the divisor grows, every item divides into a smaller piece, so the sum can only shrink or stay the same. It never jumps back up. That steady one-direction behavior is called monotonic, and it is exactly what lets us use binary search. Binary search is like guessing a number between 1 and 100 where each guess tells you "too high" or "too low," so you can throw away half the choices every time instead of checking them one by one.

mediumBinary SearchBinary SearchTime: O(n log max) · Space: O(1)

Signals to notice

smallest divisor keeping sum ≤ thresholdbinary search on divisorceiling division

Brute force first

Try every divisor from 1 to max(nums) — O(max × n).

The key insight

Binary search on divisor in [1, max(nums)]. For each candidate, compute sum of ceil(nums[i]/divisor). If sum ≤ threshold, divisor works (try smaller). O(n log max).

Trace it on `nums=[1,2,5,9], threshold=6`

init: left=1, right=max(nums)=9
mid=(1+9)//2=5 -> sum=ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5)=1+1+1+2=5; 5<=6 -> right=5
mid=(1+5)//2=3 -> sum=ceil(1/3)+ceil(2/3)+ceil(5/3)+ceil(9/3)=1+1+2+3=7; 7>6 -> left=4
mid=(4+5)//2=4 -> sum=ceil(1/4)+ceil(2/4)+ceil(5/4)+ceil(9/4)=1+1+2+3=7; 7>6 -> left=5
left==right==5 -> loop ends
return left=5

What must stay true

Larger divisor → smaller sum (monotonic). Binary search finds the smallest divisor where sum ≤ threshold.

Shape of the loop

left, right = 1, max(nums)
while left < right:
    mid = (left + right) // 2
    total = sum(ceil(num / mid) for num in nums)
    if total <= threshold: right = mid    # mid works, try smaller
    else:                  left = mid + 1  # too big a sum, need larger divisor
return left

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using floor division instead of ceiling — each element contributes ceil(num/d), not floor.

Binary Search Pattern