DSA interview question

Find the Smallest Divisor Given a Threshold

Medium · Algorithms · Topics: binary search on answer, array

The problem

A load balancer splits each incoming job of size nums[i] into chunks of at most d units, and each chunk costs one scheduling slot: ceil(nums[i] / d) slots per job. The operations team wants the smallest chunk size d that keeps the total slot count within a threshold, because smaller chunks balance the load better. A larger d always means fewer (or equal) slots, so feasibility is monotonic, and binary search on d between 1 and the largest job finds the answer.

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

Function signature

int smallestDivisor(const vector<int>& nums, long long threshold);  // threshold >= nums.size()

Test cases

Input `(nums, threshold)`	Output	Explanation
`([1, 2, 5, 9], 6)`	5	1 + 1 + 1 + 2 = 5 ≤ 6; with d = 4 the sum is 7
`([44, 22, 33, 11, 1], 5)`	44	Each element must round up to exactly 1
`([21212, 10101, 12121], 1000000)`	1	Even d = 1 is within the threshold
`([2, 3, 5, 7, 11], 11)`	3	1 + 1 + 2 + 3 + 4 = 11

(Confirm: threshold ≥ number of elements, so d = max(nums) always works; each term is ceil(nums[i] / d).)

How interviewers phrase it

"Find the smallest divisor such that the sum of the ceilings of the division results is at most the threshold" (LeetCode 1283).
Structurally identical to Koko eating bananas.

Clarifying questions to ask

Is each division rounded up?
Is the threshold guaranteed to be at least the number of elements?
How large can the values be? (The sum needs 64 bits.)

Follow-ups to expect

"Why is it monotonic?"
"What's the search range?"
"How is this the same as Koko?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview