Pattern visualizer
Find the Smallest Divisor Given a Threshold
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?'. 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..
Binary search the answer, not the array
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.
1FUNCTION smallestDivisor(nums, threshold)2 low <- 13 high <- MAX(nums)4 WHILE low <= high5 mid <- FLOOR((low + high) / 2)6 total <- SUM(CEIL(nums[i] / mid))7 IF total <= threshold8 high <- mid - 19 ELSE10 low <- mid + 111 RETURN low
← / → step · space play · Home restart