Find the Smallest Divisor Given a Threshold

medium

Find the smallest divisor such that sum of ceil(nums[i]/divisor) is within threshold

Smallest Divisor Given a Threshold

Key Insight

Binary search divisor; feasibility is monotonic because larger divisors never increase required sum.

Step 1Setup
Threshold = 6
L
1
0
2
1
5
2
9
3
Search space: [1..9]

Binary search divisor from 1 to max(nums).

1 / 3

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Smallest Divisor Given a Threshold

Binary search divisor; feasibility is monotonic because larger divisors never increase required sum.

  1. Setup

    Binary search divisor from 1 to max(nums).

  2. Try mid=5

    Compute ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5)=1+1+1+2=5 <= 6. Try smaller.

  3. Converge

    Move through search space until smallest valid divisor remains.