Find the smallest divisor
MediumBinary search the divisor
Problem
Given an array of integers nums and an integer limit as the threshold value, find the smallest positive integer divisor such that upon dividing all the elements of the array by this divisor, the sum of the division results is less than or equal to the threshold value. After dividing each element by the chosen divisor, take the ceiling of the result (i.e., round up to the next whole number).
Bigger divisors give smaller sums, so binary-search the smallest divisor whose sum fits the limit.
The idea
Dividing by a larger number always gives a smaller sum of ceilings, so the predicate 'sum with divisor d is within the limit' is monotone in d. Binary search the smallest d for which it holds.
The trick
- The search space is 1 to max(nums).
- Bigger divisor, smaller sum — that monotonicity is the licence to binary search.
- O(n log max) instead of O(n · max).
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.
Try every divisor.
1// try every divisor from 1 up2for (let d = 1; d <= maxNum; d++)3 if (sumOfCeils(d) <= limit) return d;4return maxNum;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.
Constraints
- 1 <= nums.length <= 5 * 10^4
- 1 <= nums[i] <= 10^6
- nums.length <= limit <= 10^6
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.