DSA Tracker

Visualize

Find the Smallest Divisor Given a Threshold

Binary search the answer, not the array

time O(n log(max(nums)))space O(1)

The array is not sorted and never gets sorted — what is sorted is the RANGE OF ANSWERS. Divide by a bigger number and every rounded-up quotient falls or stays put, so the total cost slides downward as the divisor grows. That one-directional slide is the only thing binary search ever needed, so the search runs over candidate divisors 1..max(nums) with 'is this divisor cheap enough?' standing in for 'is this the target?'.

Details

Animated on: nums = [9,3,5,44,6,2], threshold = 12 — find the smallest divisor d such that the sum of every nums[i] / d, each rounded up, stays at or below 12.

Problem:Find the Smallest Divisor Given a ThresholdMedium

Pattern:Binary Search on Answer

Binary search the answer, not the array

step 1 / 9

9
[0]
3
[1]
5
[2]
44
[3]
6
[4]
2
[5]

nums=[9,3,5,44,6,2], threshold=12. With divisor 1 nothing shrinks, so the cost is the whole sum 69 — way over 12. The divisor has to grow.

Pseudocode
1FUNCTION smallestDivisor(nums, threshold)
2  low <- 1
3  high <- MAX(nums)
4  WHILE low <= high
5    mid <- FLOOR((low + high) / 2)
6    total <- SUM(CEIL(nums[i] / mid))
7    IF total <= threshold
8      high <- mid - 1
9    ELSE
10      low <- mid + 1
11  RETURN low

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. nums=[9,3,5,44,6,2], threshold=12. With divisor 1 nothing shrinks, so the cost is the whole sum 69 — way over 12. The divisor has to grow.
  2. A divisor above 44 can never help: every element is already down to 1 there, cost 6. So the answer lives in 1..44, and raising the divisor never RAISES the cost — that monotonic slide is what binary search needs.
  3. Try divisor 22 on 1..44: quotients [1,1,1,2,1,1] sum to 7, within 12. It works, so nothing above 22 can be the SMALLEST answer — drop the whole upper half, high = 21.
  4. Try divisor 11 on 1..21: quotients [1,1,1,4,1,1] sum to 9, within 12. It works, so nothing above 11 can be the SMALLEST answer — drop the whole upper half, high = 10.
  5. Try divisor 5: quotients [2,1,1,9,2,1] sum to 16, over 12 — nums[3]=44 alone still costs 9. Too small a divisor, and anything smaller is worse, so low = 6.
  6. Try divisor 8 on 1..10: quotients [2,1,1,6,1,1] sum to 12, within 12. It works, so nothing above 8 can be the SMALLEST answer — drop the whole upper half, high = 7.
  7. Try divisor 6: quotients [2,1,1,8,1,1] sum to 14, over 12 — nums[3]=44 alone still costs 8. Too small a divisor, and anything smaller is worse, so low = 7.
  8. Try divisor 7: quotients [2,1,1,7,1,1] sum to 13, over 12 — nums[3]=44 alone still costs 7. Too small a divisor, and anything smaller is worse, so low = 8.
  9. low passed high, so every divisor below 8 was proved too expensive and 8 itself was proved affordable. Answer 8: quotients [2,1,1,6,1,1] sum to 12 <= 12.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find the Smallest Divisor Given a Threshold in the editorAll Binary Search problemsBack to roadmap