Find the Smallest Divisor Given a Threshold
MedPrompt
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 <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible divisor starting from 1. For each divisor, we calculate the sum of the divisions. The first divisor that results in a sum less than or equal to the threshold is the smallest one, so we can return it immediately.
Algorithm
- Start with a
divisorof 1. - Enter a loop that continues indefinitely.
- Inside the loop, calculate the sum of divisions for the current
divisor. For each numbernuminnums, addceil(num / divisor)to a running total.ceil(a/b)can be calculated using integer arithmetic as(a + b - 1) / b. - Check if the calculated
sumis less than or equal to thethreshold. - If it is, we have found the smallest divisor. Return the current
divisor. - If not, increment the
divisorand continue the loop.
Walkthrough
We are looking for the smallest positive integer divisor. The search space for the divisor starts at 1. The upper bound can be determined by the largest number in the input array, nums, because any divisor larger than max(nums) will result in a sum of nums.length, which is guaranteed to be less than or equal to threshold.
The algorithm iterates through each potential divisor d from 1 upwards. For each d, it computes the sum of ceil(num / d) for all num in nums.
The ceiling of a division a / b can be calculated using integer arithmetic as (a + b - 1) / b. This avoids floating-point inaccuracies.
As soon as a divisor is found for which the calculated sum is within the threshold, that divisor is returned. Since we are iterating in increasing order, the first one we find will be the smallest.
class Solution { // Helper function to calculate the sum for a given divisor private int calculateSum(int[] nums, int divisor) { int sum = 0; for (int num : nums) { // Calculate ceiling division: ceil(num / divisor) sum += (num + divisor - 1) / divisor; } return sum; } public int smallestDivisor(int[] nums, int threshold) { // The smallest possible divisor is 1. // We can iterate from 1 upwards until we find a valid divisor. int divisor = 1; while (true) { int sum = calculateSum(nums, divisor); if (sum <= threshold) { return divisor; } divisor++; } }}Complexity
Time
O(M * N), where N is the number of elements in `nums` and M is the value of the smallest divisor found. In the worst case, M can be as large as the maximum element in `nums`, making this approach very slow.
Space
O(1), as we only use a constant amount of extra space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will likely result in a 'Time Limit Exceeded' error on large test cases.
The number of iterations can be very large, up to the maximum value in
nums.
A more efficient approach uses binary search on the range of possible answers for the divisor. The key observation is that the sum of divisions is a monotonically decreasing function of the divisor. A larger divisor results in a smaller or equal sum. This property allows us to efficiently search for the smallest divisor that satisfies the condition.
Algorithm
- Determine the search range for the divisor. The lower bound
lowis 1. The upper boundhighcan be the maximum value in thenumsarray. - Initialize a variable
resultto store the smallest valid divisor found so far, initially set tohigh. - Perform a binary search while
low <= high:- a. Calculate the middle point
mid = low + (high - low) / 2. - b. Calculate the sum of divisions using
midas the divisor. For eachnuminnums, add(num + mid - 1) / midto the sum. - c. If the
sumis less than or equal tothreshold: i.midis a valid divisor. It could be the smallest, so updateresult = mid. ii. Try to find an even smaller divisor by narrowing the search to the left half:high = mid - 1. - d. If the
sumis greater thanthreshold: i.midis too small. We need a larger divisor. ii. Narrow the search to the right half:low = mid + 1.
- a. Calculate the middle point
- After the loop terminates,
resultwill hold the smallest divisor that satisfies the condition.
Walkthrough
The problem asks for the smallest divisor that meets a certain condition. This structure suggests that we can search for this divisor value. Let's analyze the relationship between the divisor and the resulting sum. If we define a function f(d) that calculates the sum for a given divisor d, we can see that if d1 < d2, then f(d1) >= f(d2). This monotonic property is perfect for binary search.
The search space for the divisor is from 1 to max(nums). The lower bound is 1, as the divisor must be a positive integer. The upper bound can be the maximum element in the array because any divisor larger than that will yield a sum of nums.length, which is a valid solution according to the problem constraints (nums.length <= threshold).
We can apply binary search on this range [1, max(nums)]. For each middle element mid (our candidate divisor), we calculate the sum.
- If
sum <= threshold, it meansmidis a potential answer. Since we want the smallest such divisor, we try to find an even smaller one by searching in the left half:[low, mid - 1]. We storemidas our current best answer. - If
sum > threshold, the divisormidis too small, leading to a large sum. We need a larger divisor, so we search in the right half:[mid + 1, high].
class Solution { // Helper function to calculate the sum for a given divisor private int calculateSum(int[] nums, int divisor) { int sum = 0; for (int num : nums) { // Calculate ceiling division: ceil(num / divisor) sum += (num + divisor - 1) / divisor; } return sum; } public int smallestDivisor(int[] nums, int threshold) { int low = 1; // The maximum possible divisor is the largest number in the array. int high = 0; for (int num : nums) { high = Math.max(high, num); } int smallestDivisor = high; while (low <= high) { int mid = low + (high - low) / 2; // Avoid division by zero, though low starts at 1. if (mid == 0) { low = 1; continue; } int sum = calculateSum(nums, mid); if (sum <= threshold) { // This divisor works. Let's try to find a smaller one. smallestDivisor = mid; high = mid - 1; } else { // This divisor is too small, the sum is too large. // We need a larger divisor. low = mid + 1; } } return smallestDivisor; }}Complexity
Time
O(N * log(M)), where N is the number of elements in `nums` and M is the maximum value in `nums`. The binary search takes O(log M) iterations, and each iteration requires O(N) time to calculate the sum.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Highly efficient, significantly reducing the search space compared to a linear scan.
Guaranteed to find the optimal solution in logarithmic time with respect to the range of possible divisors.
Cons
Slightly more complex to conceptualize and implement than the brute-force approach.
Solutions
Solution
public class Solution { public int SmallestDivisor(int[] nums, int threshold) { int l = 1; int r = nums.Max(); while (l < r) { int mid = (l + r) >> 1; int s = 0; foreach(int x in nums) { s += (x + mid - 1) / mid; } if (s <= threshold) { r = mid; } else { l = mid + 1; } } return l; }}class Solution {public int smallestDivisor(int[] nums, int threshold) { int l = 1, r = 1000000; while (l < r) { int mid = (l + r) >> 1; int s = 0; for (int x : nums) { s += (x + mid - 1) / mid; } if (s <= threshold) { r = mid; } else { l = mid + 1; } } return l; }}/** * @param {number[]} nums * @param {number} threshold * @return {number} */ var smallestDivisor = function ( nums , threshold ) { let l = 1 ; let r = Math . max (... nums ); while ( l < r ) { const mid = ( l + r ) >> 1 ; let s = 0 ; for ( const x of nums ) { s += Math . ceil ( x / mid ); } if ( s <= threshold ) { r = mid ; } else { l = mid + 1 ; } } return l ; };class Solution: def smallestDivisor(self, nums: List[int], threshold: int) -> int: l, r = 1, max(nums) while l < r: mid = (l + r) >> 1 if sum((x + mid - 1) // mid for x in nums) <= threshold: r = mid else: l = mid + 1 return lclass Solution {public: int smallestDivisor(vector<int> &nums, int threshold) { int l = 1; int r = *max_element(nums.begin(), nums.end()); while (l < r) { int mid = (l + r) >> 1; int s = 0; for (int x : nums) { s += (x + mid - 1) / mid; } if (s <= threshold) { r = mid; } else { l = mid + 1; } } return l; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.