Find the Smallest Divisor Given a Threshold

Problem Statement

The task at hand is to determine the smallest possible integer divisor so that when each element of a given integer array nums is divided by this divisor, and each resultant value is rounded up to the nearest greater integer, the sum of all these rounded results does not exceed a given integer threshold.

Division rounding here implies that for each division, you round the result to the nearest integer that is greater than or equal to the actual division result (for instance, the division of 7 by 3 results in 3 and 10 by 2 results in 5). This problem carries the assurance that a valid solution, a divisor that satisfies the conditions, always exists.

Examples

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 * 104
• 1 <= nums[i] <= 106
• nums.length <= threshold <= 106

Approach and Intuition

The strategy to solve the problem involves understanding the relationships between the divisor, the division results, and the sum relative to the threshold:

1. Understanding the Direct Relationship: The smaller the divisor, the larger the division result of any element in nums. This leads to a higher sum.

2. Initial Setup: Begin by considering the possible range for the divisor. The smallest potential divisor could be 1 (which will give the maximum possible sum), and the largest practical divisor could be the maximum number within nums (which guarantees a sum of at least nums.length, since each term will at minimum contribute 1).

3. Binary Search Implementation: To efficiently find the smallest divisor, employ a binary search over the range of potential divisors:

   • Mid Calculation: In each iteration, calculate the mid of your current divisor range.

   • Sum Calculation: For this mid value, compute the sum of each term in nums divided by mid, rounded up.

   • Range Adjustment: If this sum exceeds the threshold, it implies that the mid is too small (since making divisor smaller increases individual division results); hence, adjust your search to the upper half of the current range. If the sum is less than or equal to the threshold, the mid might be a valid solution but there could be an even smaller valid divisor, thus, adjust your search to explore the lower half.

   • Stop Condition: The process continues until the search range is narrowed down efficiently to the smallest divisor that produces a sum that is just beneath or matches the threshold.

4. Solution Validity: By approach design (binary search within constrained sums), the solution is guaranteed to be the smallest valid divisor.

Employing this approach ensures efficient handling of the large potential input sizes, fitting within the provided constraints.

Solutions

class Solution {
public:
    int sumDivisions(vector<int>& nums, int divisor) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += ceil(num / (double) divisor);
        }
        return totalSum;
    }
    
    int findSmallestDivisor(vector<int>& nums, int threshold) {
        int left = 1;
        int right = *max_element(nums.begin(), nums.end());
        int selectedDivisor = -1;
    
        while (left <= right) {
            int middle = (left + right) / 2;
            int tempResult = sumDivisions(nums, middle);
            if (tempResult <= threshold) {
                selectedDivisor = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
    
        return selectedDivisor;
    }
};