DAY 77 - Find the Smallest Divisor Given a Threshold

Hey Guys! It's day 77 and we are going to do another binary search question.

Question: Finding Smallest Divisor to Meet Threshold

The problem involves finding the smallest divisor that, when applied to each element in an array, ensures that the sum of the divided values does not exceed a given threshold. Given an array nums of integers and an integer threshold, the task is to determine the smallest divisor that satisfies the threshold constraint.

Approach Overview

The problem can be addressed through a binary search approach. The main idea is to search for the optimal divisor within a certain range. The algorithm should determine whether dividing each element by a particular divisor results in a sum that is within the threshold limit.

The approach involves the following steps:

1. Initialize the search range for the divisor. The lower bound can be set as 1 (minimum possible divisor), and the upper bound can be set as the maximum element in the array.

2. Perform a binary search within the defined divisor range. Calculate the sum of divided values using the calcThreshold function at the current divisor.

3. If the calculated sum is less than or equal to the given threshold, the current divisor is feasible. Move the upper bound of the search range to explore smaller divisors.

4. If the calculated sum is greater than the threshold, the current divisor is not feasible. Move the lower bound of the search range to explore larger divisors.

5. Repeat steps 2-4 until the lower bound is less than or equal to the upper bound.

6. The final value of the lower bound will represent the smallest divisor that meets the threshold constraint.

---

Code:

class Solution {
public:
    long long calcThreshold(vector<int>& nums, int div){
    long long ans = 0;
    for(auto& it: nums){
        ans += (it + div - 1) / div;  // Corrected division
    }
    return ans;
}
    int smallestDivisor(vector<int>& nums, int threshold) {
        int n = nums.size();
        if (n > threshold) return -1;
        int low = 1;
        int high = *max_element(nums.begin(),nums.end());

        while(low <= high){
            int mid = low + (high-low)/2;
            if(calcThreshold(nums,mid) <= threshold){
                high =  mid-1;
            }
            else{
                low = mid+1;
            }
        }
        return low;
    }
};

Complexity Analysis:

Algorithm	Time Complexity	Space Complexity
Binary Search Approach	O(nlog(m)	O(1)