358. Gentle Divisor
A teacher wants to scale down a list of scores using one whole number d. Each score nums[i] is divided by d and rounded up to the next whole number, and the scaled scores are then added together.
Given nums and an integer threshold, return the smallest positive integer d for which the total of the rounded-up quotients is at most threshold. It is guaranteed that such a d exists, because threshold is never less than the number of scores. Try to do better than checking d = 1, 2, 3, ... in order.
Example 1
- Input:
- nums = [8,17,5,12], threshold = 7
- Output:
- 8
- Explanation:
With d = 6 the quotients are 2, 3, 1, 2 which sum to 8, too many; with d = 8 they are 1, 3, 1, 2 = 7, so 8 is the smallest divisor.
Example 2
- Input:
- nums = [3,3], threshold = 2
- Output:
- 3
- Explanation:
Dividing by 3 gives 1 + 1 = 2, which fits.
Constraints
1 ≤ nums.length ≤ 5 * 105
nums.length ≤ threshold ≤ 106
1 ≤ nums[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log M), where M is the largest score
- Space
- O(1)