---

1. Problem Summary

You are given:

• an integer array nums
• an integer threshold

Your task is to find the smallest positive integer divisor such that:

sum( ceil(nums[i] / divisor) ) <= threshold

Important characteristics:

• Division results are rounded up (ceiling division)
• Divisor must be a positive integer
• As divisor increases, the computed sum decreases
• You must return the minimum divisor that satisfies the condition

Example interpretation:
If nums = [1,2,5,9] and threshold = 6, the smallest divisor that keeps the ceiling-sum ≤ 6 is 5.

---

2. Key Insights

Ceiling division is required

Formula:

ceil(a / b) = (a + b - 1) / b   (integer math trick)

Relationship between divisor and sum

• Smaller divisor → larger division results → larger total sum
• Larger divisor → smaller total sum

Meaning:

sum(divisor) is monotonic decreasing

Monotonic behavior allows Binary Search

We can search divisor space efficiently by:

• guessing a divisor
• computing the resulting sum
• narrowing range based on threshold comparison

Search space boundaries

Minimum divisor = 1
Maximum divisor = max(nums)

---

3. Approach

Binary Search on divisor value

Steps:

1. Set search boundaries: left = 1 right = max(nums)
2. While left < right:
   • mid = (left + right) / 2
   • compute computedSum using ceiling division
   • if computedSum <= threshold:
     move right = mid (try smaller divisor)
     else:
     move left = mid + 1 (need bigger divisor)
3. Return left (or right) as smallest valid divisor

---

4. Time and Space Complexity

Time Complexity: O(N log M)

Where:

• N = number of elements in nums
• M = max(nums)

Explanation:

• For each binary search step, we compute sum in O(N)
• Binary search performs log(M) iterations

Space Complexity: O(1)

Only constant variables are used.

---

5. Java Solution

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1;
        int right = 0;

        for (int num : nums) {
            right = Math.max(right, num);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;

            int sum = 0;
            for (int num : nums) {
                sum += (num + mid - 1) / mid;  // ceiling division
            }

            if (sum <= threshold) {
                right = mid;   // try smaller divisor
            } else {
                left = mid + 1;  // need bigger divisor
            }
        }

        return left;
    }
}

---

6. Dry Run Examples

Example 1

Input:

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

Search range:
left=1, right=9

mid=5
sum = ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5)
= 1 + 1 + 1 + 2 = 5 ≤ threshold
→ move right = 5

mid between 1 and 5 = 3
sum = 1 + 1 + 2 + 3 = 7 > threshold
→ move left = 4

mid between 4 and 5 = 4
sum = 1 + 1 + 2 + 3 = 7 > threshold
→ left = 5

Final answer:

5

---

Example 2

Input:

nums = [2,3,5,7,11]
threshold = 11

Try divisor 3:
sum = 1 + 1 + 2 + 3 + 4 = 11
Valid, try smaller

Continue narrowing…

Final answer:

3

---

Example 3

Input:

nums = [19]
threshold = 5

Single number:

ceil(19 / divisor) ≤ 5
Smallest divisor = 4

Output:

4

---

Example 4

Input:

nums = [8,4,2,3]
threshold = 10

Even divisor 1 gives sum = 17
Binary search finds minimal divisor = 1

Output:

1

---

7. Why This Solution Works

• Uses monotonic decreasing property of sum(divisor)
• Binary search narrows space efficiently
• Ceiling division ensures correct rounding
• Avoids brute force iteration across all divisors
• Handles large input values safely

---

8. Common Mistakes

1. Using floating-point division instead of integer ceiling
2. Forgetting to start right as max(nums)
3. Incorrect binary search direction adjustments
4. Miscomputing ceil with integer division
5. Returning mid instead of left/right end value

Correct ceiling formula:

ceil(a / b) = (a + b - 1) / b