Code Implementation

class Solution:
    def smallestDivisor(self, nums, threshold):
        import math
        def compute_sum(divisor):
            return sum((num + divisor - 1) // divisor for num in nums)
        
        left, right = 1, max(nums)
        answer = right
        
        while left <= right:
            mid = (left + right) // 2
            if compute_sum(mid) <= threshold:
                answer = mid
                right = mid - 1
            else:
                left = mid + 1
        return answer
      

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        auto compute_sum = [&](int divisor) {
            int total = 0;
            for (int num : nums) {
                total += (num + divisor - 1) / divisor;
            }
            return total;
        };
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int answer = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (compute_sum(mid) <= threshold) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
};
      

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        int answer = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int total = 0;
            for (int num : nums) {
                total += (num + mid - 1) / mid;
            }
            if (total <= threshold) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
}
      

var smallestDivisor = function(nums, threshold) {
    const computeSum = (divisor) => {
        let total = 0;
        for (let num of nums) {
            total += Math.floor((num + divisor - 1) / divisor);
        }
        return total;
    };
    let left = 1, right = Math.max(...nums);
    let answer = right;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (computeSum(mid) <= threshold) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
};
      

Problem Description

Given an array of positive integers nums and an integer threshold, your goal is to find the smallest positive integer divisor such that the sum of all the elements in nums divided by this divisor (and rounded up to the nearest integer for each element) is less than or equal to threshold.

In other words, for each number num in nums, compute ceil(num / divisor), sum all these values, and make sure the total does not exceed threshold. You need to find the smallest possible divisor that satisfies this condition.

• There is always exactly one valid solution.
• You may not reuse the same divisor for different numbers; the divisor must be the same for all elements.

Thought Process

At first glance, it seems like you might have to try every possible divisor from 1 up to the largest number in nums and check if it meets the condition. However, this would be inefficient, especially for large arrays or large numbers.

We notice that as the divisor increases, the result of ceil(num / divisor) for each num decreases or stays the same. This means that the total sum of these values will decrease as the divisor increases. This monotonic (always decreasing or staying the same) property hints that we can use binary search to find the smallest divisor efficiently.

Instead of brute-forcing every possible divisor, we can repeatedly narrow down the range of possible divisors by checking the mid-point, similar to how you might guess a number in a "higher or lower" game.

Solution Approach

• Step 1: Define the Search Range
  • The smallest possible divisor is 1 (which gives the largest possible sum).
  • The largest possible divisor is the maximum value in nums (which gives the smallest possible sum).
• Step 2: Binary Search
  • While the search range is valid (left <= right), do the following:
  • Find the mid-point (mid) of the current range.
  • For each num in nums, compute ceil(num / mid) (or equivalently, (num + mid - 1) // mid without using floating point).
  • Sum these values to get the total.
  • If the total is less than or equal to threshold, try a smaller divisor by moving the right boundary to mid - 1.
  • Otherwise, try a larger divisor by moving the left boundary to mid + 1.
• Step 3: Return the Answer
  • Track the smallest divisor found that meets the condition.
  • Once the search is complete, return this value.
• Why Binary Search?
  • Because the function mapping divisor to sum is monotonic (never increases as divisor increases), binary search is guaranteed to find the smallest valid divisor efficiently.

Example Walkthrough

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

1. Initial Range: divisor from 1 to 9 (since max(nums) = 9)
2. First Iteration:
   • mid = (1 + 9) // 2 = 5
   • Sum = ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5
   • 5 ≤ 6, so try smaller divisor (right = 4), answer = 5
3. Second Iteration:
   • mid = (1 + 4) // 2 = 2
   • Sum = ceil(1/2) + ceil(2/2) + ceil(5/2) + ceil(9/2) = 1 + 1 + 3 + 5 = 10
   • 10 > 6, so try larger divisor (left = 3)
4. Third Iteration:
   • mid = (3 + 4) // 2 = 3
   • Sum = ceil(1/3) + ceil(2/3) + ceil(5/3) + ceil(9/3) = 1 + 1 + 2 + 3 = 7
   • 7 > 6, so try larger divisor (left = 4)
5. Fourth Iteration:
   • mid = 4
   • Sum = ceil(1/4) + ceil(2/4) + ceil(5/4) + ceil(9/4) = 1 + 1 + 2 + 3 = 7
   • 7 > 6, so try larger divisor (left = 5)
6. End: left = 5, right = 4, loop ends. The answer is 5.

So, the smallest divisor is 5.

Time and Space Complexity

• Brute-force Approach:
  • Try every divisor from 1 to max(nums). For each, sum over all elements: O(N * M), where N = len(nums), M = max(nums).
  • This is very slow for large inputs.
• Optimized (Binary Search) Approach:
  • Binary search over divisors: O(log M), where M = max(nums).
  • For each binary search step, compute the sum in O(N) time.
  • Total time: O(N * log M).
  • Space: O(1), aside from input storage.

Summary

The key insight is recognizing the monotonic relationship between the divisor and the total sum of rounded-up divisions. This enables a binary search for efficiency, reducing the time complexity from potentially millions of checks to just a few dozen, even for large inputs. The approach is elegant because it leverages mathematical properties (monotonicity) and simple integer math to avoid floating-point issues, resulting in a robust and fast solution.