1283. Find the Smallest Divisor Given a Threshold

Given an array of integers `nums` and an integer `threshold`, we will choose a positive integer `divisor`, divide all the array by it, and sum the division’s result. Find the smallest `divisor` such that the result mentioned above is less than or equal to `threshold`.

Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: `7/3 = 3` and `10/2 = 5`).

The test cases are generated so that there will be an answer.

Example 1:

``````Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
``````

Example 2:

``````Input: nums = [44,22,33,11,1], threshold = 5
Output: 44
``````

Constraints:

• `1 <= nums.length <= 5 * 10^4`
• `1 <= nums[i] <= 10^6`
• `nums.length <= threshold <= 10^6`

``````class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int left = 1, right = 1e6;
while (left < right) {
int mid = left + (right - left) / 2, sum = 0;
for (int num : nums) {
sum += (num + mid - 1) / mid;
}
if (sum > threshold) left = mid + 1;
else right = mid;
}
return left;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1283

Minimized Maximum of Products Distributed to Any Store

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/discuss/446376/JavaC%2B%2BPython-Binary-Search

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation