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 * 1041 <= nums[i] <= 106nums.length <= threshold <= 106This approach uses binary search to efficiently find the smallest divisor. The possible divisors can range from 1 to the maximum number in the array. For each candidate divisor, divide each number in the array, take the ceiling of the division result, sum it up, and compare against the threshold.
Binary search helps minimize the number of trials by adjusting the divisor range based on whether the threshold condition is met or not for a given divisor.
The code uses binary search to find the smallest divisor. The loop continues until 'left' and 'right' converge. For each middle value, we compute the sum of divisions rounded up (utilizing integer arithmetic for efficiency), and adjust the search range based on whether this sum is more or less than the threshold.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space.
This method involves a simple linear search from divisor = 1 upwards, incrementally checking each candidate as a divisor. This approach is less efficient compared to binary search but helps understand the problem in a straightforward manner. We calculate the total sum of the divisions for each divisor and stop when the sum is less or equal to the threshold. Ensuring progressively checking divisors until a valid one is found assures correctness.
This code initiates a loop to test each divisor starting from 1 upwards until it finds the smallest divisor satisfying the condition. The ceiling of division is calculated with the same integer math trick as before.
C++
Java
Python
C#
JavaScript
Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search | Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space. |
| Approach 2: Linear Scan with Improved Accuracy | Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1). |
BS-14. Find the Smallest Divisor Given a Threshold | Binary Search • take U forward • 116,893 views views
Watch 9 more video solutions →Practice Find the Smallest Divisor Given a Threshold with our built-in code editor and test cases.
Practice on FleetCode