You are given an array of positive integers nums and an integer threshold.
Choose a positive integer divisor, divide every element of nums by it, and add up the results — where each division is rounded up to the nearest integer (so 7 / 3 counts as 3, and 10 / 2 is 5).
Return the smallest divisor such that this sum is less than or equal to threshold.
It is guaranteed that an answer always exists.
d = max(nums) every term ceil(nums[i] / d) is exactly 1, so the sum equals nums.length — and the constraint nums.length <= threshold guarantees that fits. Any larger divisor still gives all 1s, so nothing beyond max(nums) can ever do better.ceil(x / d) equals (x + d - 1) // d. Adding d - 1 pushes any nonzero remainder over to the next integer, and it avoids float precision issues entirely.1 the sum is the plain array sum — up to 5 * 10^4 * 10^6 = 5 * 10^10, which overflows 32-bit integers. Accumulate in long long in C++; Python, JavaScript numbers, and Go's 64-bit int are fine.nums — we search the range of candidate divisors 1..max(nums). What must be monotone is the feasibility check sum(d) <= threshold as a function of d, and it is: a bigger divisor never increases the sum.k in 1..max(piles), where the feasibility check is whether sum(ceil(pile / k)) hours fits within h. Recognising the shared fails-then-fits shape is the interview win.x // d. The habit to build: re-verify monotonicity whenever the cost function changes, because that is the only property the search needs.(x + d - 1) // d for ceiling division is a classic from low-level systems code, where it computes how many fixed-size blocks are needed to hold x bytes.Input: nums = [1,2,5,9], threshold = 6 Output: 5 With divisor 1 the sum is 17 (1+2+5+9). With divisor 4 it is 7 (1+1+2+3) — still too big. With divisor 5 it is 5 (1+1+1+2), which fits, and no smaller divisor works.
Input: nums = [44,22,33,11,1], threshold = 5 Output: 44 The sum can never drop below 5 — each of the 5 elements contributes at least 1. So every element must shrink to exactly 1, and that first happens at divisor 44 (since ceil(44/43) = 2 is still too much).
- 1 <= nums.length <= 5 * 10^4 - 1 <= nums[i] <= 10^6 - nums.length <= threshold <= 10^6
This problem is the cleanest introduction to a powerful idea: when the answer lives on a number line and bigger candidates only make a check easier, you can binary search the answer itself — no sorted array required.
ceil(x / d) equals (x + d - 1) // d for positive integers.In plain English: pick a positive integer d, replace every element x with ceil(x / d), and sum the results. Among all d whose sum is at most threshold, return the smallest. The guarantee nums.length <= threshold means an answer always exists.
Worked example — nums = [1,2,5,9], threshold = 6
divisor d : 1 2 3 4 5 6 ...
sum(d) : 17 10 7 7 5 5 ...
fits ≤ 6? : ✗ ✗ ✗ ✗ ✓ ✓
^ first ✓ → answer 5
Asking two or three sharp questions before coding shows you verify the ground you are about to build on.
“Is a valid divisor guaranteed to exist?”
Yes — threshold >= nums.length, and at d = max(nums) every term becomes 1, so the sum is exactly nums.length. Without this guarantee the search would need a not-found convention.
“Are all elements strictly positive?”
Yes, nums[i] >= 1 — so every term is at least 1 and there are no zero or negative rounding wrinkles.
“What if nums has a single element?”
The answer is the smallest d with ceil(nums[0] / d) <= threshold — the same algorithm handles it with no special case.
“Can the answer be 1?”
Yes — if the plain sum of nums already fits under threshold, dividing by 1 is optimal. Make sure the search range starts at 1.
“How large can n and the values get?”
n up to 5 * 10^4 and values up to 10^6. Trying every divisor costs up to ~5 * 10^10 operations — far too slow — while O(n log max) is about a million. The constraints all but announce binary search.
“Can the sum overflow a 32-bit integer?”
At d = 1 the sum can reach 5 * 10^10 — accumulate in a 64-bit integer in fixed-width languages.
Before I code, a few clarifying questions.
Am I guaranteed a valid divisor exists — is threshold always at least the array length?
Since the sum with divisor one can be around five times ten to the tenth, I will accumulate in a 64-bit integer.
The sum only shrinks as the divisor grows, so I plan to binary search the divisor rather than scan every candidate.
Increase d and every single term ceil(x / d) either stays the same or gets smaller — so the total never increases. That makes the fits-under-threshold check monotone: the candidates form a clean row of failures followed by a clean row of successes.
d: 1 2 3 4 5 6 7 ...
fits?: ✗ ✗ ✗ ✗ ✓ ✓ ✓ ...
no ✓ ever appears before the boundaryAt d = max(nums), every term ceil(x / d) is exactly 1, so the sum equals nums.length — and the guarantee nums.length <= threshold means this always fits. Any divisor beyond max(nums) still produces all 1s, so it can never beat max(nums). The search space is bounded and finite.
Finding the first ✓ in a ✗✗✗✓✓✓ row is the classic lower-bound search. Probe the middle divisor mid: if it fits, the answer is mid or something smaller (hi = mid); if it fails, everything up to mid fails too (lo = mid + 1). Each probe costs one O(n) sum, and about log2(10^6) ≈ 20 probes pin down the boundary.
| Brute force | Optimal | |
|---|---|---|
| Time | O(n · max(nums)) | O(n log max(nums)) |
| Space | O(1) | O(1) |
With max(nums) up to 10^6 and n up to 5 * 10^4, the brute-force dial-turning performs up to ~5 * 10^10 term computations; binary search needs about 20 passes over the array. Full code for both lives in the Approaches selector below.
Key takeaway
Binary search on the answer: when a feasibility check is monotone over a numeric range — bigger candidate, easier (or harder) check — binary search the range for the boundary instead of scanning it. The array is never sorted; the answer space is.
lo = 1, hi = max(nums)
while lo < hi:
mid = (lo + hi) / 2
if sum(ceil(x / mid) for x in nums) <= threshold:
hi = mid # mid fits — a smaller divisor might too
else:
lo = mid + 1 # mid too small — sum still over budget
return lo