What is the main approach to solve the 'Find the Smallest Divisor Given a Threshold' problem?

The main approach is binary search over the valid divisors, ensuring each check involves computing the sum of the divisions and adjusting the bounds based on the threshold.

How can I efficiently calculate the sum of the divisions?

For each element, divide it by the candidate divisor and round up. Then, sum these results and compare them to the threshold.

Why does binary search work well in this problem?

Binary search efficiently narrows down the smallest divisor by repeatedly halving the search space, making it well-suited for this type of problem.

What is the time complexity of the solution?

The time complexity is `O(n log(max(nums)))`, where `n` is the number of elements and `max(nums)` is the maximum element in the array.

What are the edge cases I should consider for this problem?

Consider edge cases such as arrays with small elements, large thresholds, and arrays with only one element, as these can affect the binary search bounds.

#1283

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

使结果不超过阈值的最小除数

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。请你找出能够使上述结果小于等于阈值 threshold 的除数中最小的那个。每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。…

数组二分查找

题目描述

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 threshold 的除数中最小的那个。

每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。

题目保证一定有解。

示例 1：

输入：nums = [1,2,5,9], threshold = 6
输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。

示例 2：

输入：nums = [2,3,5,7,11], threshold = 11
输出：3

示例 3：

输入：nums = [19], threshold = 5
输出：4

提示：

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

lightbulb

解题思路

方法一：二分查找

我们注意到，对于一个数字 $v$ ，如果将 $nums$ 中的每个数字都除以 $v$ 的结果之和小于等于 $threshold$ ，那么所有大于 $v$ 的值都满足条件。这存在着单调性，因此我们可以使用二分查找的方法找到最小的满足条件的 $v$ 。

我们定义二分查找的左边界 $l=1$ , $r=\max(nums)$ ，每次取 $mid=(l+r)/2$ ，计算 $nums$ 中每个数字除以 $mid$ 的结果之和 $s$ ，如果 $s$ 小于等于 $threshold$ ，那么说明 $mid$ 满足条件，我们将 $r$ 更新为 $mid$ ，否则将 $l$ 更新为 $mid+1$ 。

最后返回 $l$ 即可。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def f(v: int) -> bool:
            v += 1
            return sum((x + v - 1) // v for x in nums) <= threshold

        return bisect_left(range(max(nums)), True, key=f) + 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate's understanding of binary search is key for solving this problem efficiently.
question_mark
Look for the candidate's ability to implement efficient summation and handle large inputs.
question_mark
Pay attention to how the candidate handles edge cases and adjusts the binary search bounds correctly.

warning

常见陷阱

外企场景

error
Misunderstanding the rounding behavior during division may lead to incorrect sums.
error
Inefficient summation of array elements for each divisor choice could slow down the solution.
error
Not adjusting the search bounds correctly during binary search could result in suboptimal solutions or failure to find the correct divisor.

swap_horiz

进阶变体

外企场景

arrow_right_alt
If the array contains only one element, the problem simplifies to finding the smallest divisor for that element alone.
arrow_right_alt
Consider cases where the threshold is very large, potentially requiring a larger divisor.
arrow_right_alt
Extend the problem to handle floating-point numbers or more complex rounding rules.

help

常见问题

外企场景

继续练习

#1292 元素和小于等于阈值的正方形的最大边长 #1268 搜索推荐系统 #1300 转变数组后最接近目标值的数组和