AlgoViz
HomeBinary Search

Smallest Divisor Given a Threshold

Medium

Bigger divisor → smaller sum

In simple words

Guess a divisor; if the totals come out small enough try a smaller one, otherwise a bigger one.

The idea

Dividing by a larger number lowers the sum of ceilings, so the sum is monotone in the divisor. Binary search the smallest divisor within the limit.

1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
candidates9

Step 1 of 5. Brute force: try every divisor from 1 up until the sum of ceilings is ≤ 6. Values: 1, 2, 3, 4, 5, 6, 7, 8, 9. candidates 9.

1/5
Brute force
timeO(max·n)spaceO(1)

Try every divisor.

1let best = -1;2for (let d = 1; d <= maxNum && best < 0; d++)3  if (sumOfCeils(d) <= limit) best = d;4return best;

Input

array
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Memory

try
—
candidates
9
divisor
—

Output

divisor
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 5, 9], limit = 6
Output:
3
Explanation:
Dividing by 5 keeps the sum of ceilings <= 6.

Example 2

Input:
nums = [44, 22, 33, 11, 1], limit = 5
Output:
44
Explanation:
Divisor 44 fits the limit.

Example 3

Input:
nums = [2, 3, 5], limit = 10
Output:
1
Explanation:
Even divisor 1 stays within 10.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.