Smallest Divisor Greater Than Threshold Optimal Binary Search Approach

You are given a list of positive integers nums and a positive integer threshold. Your task is to find the smallest positive integer divisor such that the sum of all elements in the array when each is divided by this divisor (rounded up) is less than or equal to threshold.

• For each number in the array, you must compute ceil(num / divisor).
• The final sum of these values must not exceed the given threshold.

If nums is empty or threshold is not a valid positive number, return -1.

Understanding the Problem

We are given an array of positive integers and a threshold. Our goal is to find the smallest positive divisor such that when each number in the array is divided by this divisor and rounded up (using the ceiling function), the total sum of these results is less than or equal to the threshold.

Let’s look at an example to make it clear. Suppose:

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

If we try divisor = 5, the results of ceiling division are:

• ceil(1 / 5) = 1
• ceil(2 / 5) = 1
• ceil(5 / 5) = 1
• ceil(9 / 5) = 2

The total sum is 1 + 1 + 1 + 2 = 5, which is less than or equal to the threshold 6. Hence, 5 is a valid divisor. But is it the smallest one? That’s what we need to figure out.

Step-by-Step Solution with Example

Step 1: Understand ceiling division

For any number x and divisor d, ceil(x/d) means rounding the result up. For example, ceil(9/4) = 3, not 2. This helps ensure that the result is always at least as large as the exact division, rounded up.

Step 2: Define the problem as a search problem

We can treat the search for the smallest divisor as a range of numbers from 1 to the max(nums). For each value in this range, we calculate the total of all ceil(num / divisor) and check if it’s less than or equal to the threshold.

Step 3: Use binary search to optimize

Trying each number one-by-one would be slow. Instead, we use binary search:

• Start with low = 1 and high = max(nums)
• At each step, pick mid = (low + high) / 2 and calculate the total sum using this mid as the divisor
• If the sum is within the threshold, try smaller divisors (high = mid - 1)
• Otherwise, try larger divisors (low = mid + 1)

Step 4: Walk through the example

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

• Start with low = 1, high = 9
• mid = 5 ➝ total = 5 (valid) ➝ try smaller (high = 4)
• mid = 2 ➝ total = ceil(1/2)+ceil(2/2)+ceil(5/2)+ceil(9/2) = 1+1+3+5 = 10 ➝ too big ➝ try larger (low = 3)
• mid = 3 ➝ total = 1+1+2+3 = 7 ➝ too big ➝ try larger (low = 4)
• mid = 4 ➝ total = 1+1+2+3 = 7 ➝ too big ➝ try larger (low = 5)

At the end, we settle on divisor = 5 as the smallest valid divisor.

Edge Cases

• Empty array: There are no elements to divide. Return -1.
• Threshold is 0 or negative: It’s impossible to satisfy the requirement. Return -1.
• All numbers are 1: Any divisor ≥ 1 results in a sum equal to the length of the array.
• Very large numbers: Binary search ensures that we only do log(max) checks, so it stays efficient.

Finally

This problem is a great example of turning a mathematical challenge into an efficient algorithm. By using binary search over possible divisors, we quickly narrow down to the smallest one that meets the threshold. This approach handles large inputs well and avoids brute-force inefficiencies.

Always remember to consider edge cases and validate inputs before applying the main logic. And when you see a problem asking for “minimum x that satisfies a condition,” binary search is often your best friend.

1. Initialize low = 1 and high = max(nums).
2. While low ≤ high:
3. → Calculate mid as the potential divisor.
4. → Compute sum = sum(ceil(num / mid) for num in nums).
5. → If sum ≤ threshold: store mid as potential answer, and search for smaller divisor by setting high = mid - 1.
6. → Else: search higher by setting low = mid + 1.
7. Return the smallest valid divisor found.

O(1)

Explanation: Only a few variables are used; no extra space proportional to input size.