1283. Find the Smallest Divisor Given a Threshold

Problem

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 smallestdivisor 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). (link)

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 * 10^4

• 1 <= nums[i] <= 10^6

• nums.length <= threshold <= 10^6

Solution

Brute Force Approach

We need to find the smallest divisor for which the sum of divisors is less than or equal to the provided threshold. Beginning with a check from 1 onwards and continuing until reaching the highest value in the array, we identify the divisor where the sum meets the condition and return that divisor.

Explanation: When dividing each element of the array by its maximum value and summing the resulting divisors, we find that it equals the length of the array. This holds true even if we select any number greater than the maximum value in the array for division.

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int max = Arrays.stream(nums).max().getAsInt();


        int divisorSum = 0;

        for(int i=1; i<=max; i++){
            divisorSum = 0;
            for(int element: nums){
                divisorSum += Math.ceil((double)element/i);
            }
            if(divisorSum<=threshold) return i;
        }

        return -1;
    }
}

Optimal Approach

This optimization involves applying the binary search algorithm to the brute force approach. We notice a pattern: as we iterate from 1 up to the maximum value, we reach a point where each number satisfies the threshold divisor sum because we increase the divisor with each iteration.

Therefore, we implement binary search, setting the low at 1 and the high at the maximum value. Additionally, we extract the divisor sum calculation into a separate method. During the search, we compare the divisor sum of the middle element with the threshold. If it exceeds the threshold, we adjust the high to the left by pointing to mid-1.

X X X X Y Y Y Y Y Y  Y
1 2 3 4 5 6 7 8 9 10 11

// From 5 each number satisfies the threshold sum

class Solution {

    public int divisorSum(int[] nums,int divisor, int threshold){
        int divisorSum = 0;
        for(int element: nums){
            divisorSum += Math.ceil((double)element/divisor);
            if(divisorSum>threshold) return divisorSum;
        }
        return divisorSum;
    }

    public int smallestDivisor(int[] nums, int threshold) {
        int max = Arrays.stream(nums).max().getAsInt();

        int low = 1;
        int high = max;

        while(low<=high){
            int mid = (low+high)/2;

            if(divisorSum(nums,mid, threshold)>threshold){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }

        return low;
    }
}