#1283

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Find the Smallest Divisor Given a Threshold

Find the smallest divisor such that the sum of all divided array elements is less than or equal to the threshold.

Problem Statement

You are given an array of integers, nums, and a positive integer threshold. Your task is to choose the smallest integer divisor such that when each element of the array is divided by this divisor, the sum of the results is less than or equal to the threshold. Each division result is rounded up to the nearest integer greater than or equal to the quotient.

For example, if nums = [1, 2, 5, 9] and threshold = 6, you need to find the smallest divisor such that dividing the elements of nums by this divisor and summing the results gives a sum no greater than 6. The goal is to find the smallest divisor using an efficient approach, considering the constraints on the input size.

Examples

Example 1

Input: nums = [1,2,5,9], threshold = 6

Output: 5

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

Example details omitted.

Constraints

1 <= nums.length <= 5 * 104
1 <= nums[i] <= 106
nums.length <= threshold <= 106

Solution Approach

Binary Search Over Divisors

Use binary search to identify the smallest divisor that satisfies the condition. The search space ranges from 1 to the largest number in the nums array. By checking the sum of the divisions for each midpoint divisor, you can adjust the search bounds to narrow down the smallest valid divisor.

Efficient Summation

For each candidate divisor, compute the sum of the array where each element is divided by the divisor and rounded up. This sum is compared against the threshold. Efficient summation is crucial to ensure the binary search process runs within acceptable time limits.

Edge Case Handling

Consider edge cases such as when all elements of the array are small or the threshold is large. Also, make sure to handle cases where the divisor must be large enough to achieve the desired sum without exceeding the threshold.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n log(max(nums))), where n is the length of the array and max(nums) is the maximum element in nums. This is because the binary search operates over a range of size log(max(nums)), and for each step of the search, we need to compute the sum of the array, which takes O(n) time. Space complexity is O(1) as we only need a few variables to store intermediate values.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Binary Search

Notice that for number $v$, if the sum of results of dividing each number in $nums$ by $v$ is less than or equal to $threshold$, then all values greater than $v$ satisfy the condition. There is a monotonicity, so we can use binary search to find the smallest $v$ that satisfies the condition.

1

2

3

4

5

6

7

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

Continue Practicing

#1292 maximum side length of a square with sum less than or equal to threshold #1268 search suggestions system #1300 sum of mutated array closest to target