Find the Smallest Divisor given a Threshold Leetcode Solution

This post is on Find the Smallest Divisor given a Threshold Leetcode Solution

Problem statement

In the problem ” Find the Smallest Divisor Given a Threshold” we are given a nums array and a threshold value. A variable “result” is defined as the sum of all answers when elements in the array are divided by a divisor. Our task is to find the smallest possible value of the divisor in such a way that the result is smaller than or equal to the threshold.

When we divide the elements in the array by a divisor, we are considering the ceiling value as the answer to division. Divisor should be a positive integer.

Example

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

5

Explanation: when we divide all the elements by 1 result is(1+2+5+9) 17 which is greater than 6. So, we will increase the value of the divisor to reduce the value of the result.

Now if we consider divisor=4 then the result is (1+1+2+3) 7, which is greater than 6. So, we will increase the value of the divisor to reduce the value of the result.

if we consider divisor=5 then the result is (1+1+1+2) 6. So the answer is 5.

Approach

Our task is to find the minimum value of the divisor. So, let’s first think about what could be the minimum and maximum value of the divisor.

• The minimum value of the divisor is 1 because the divisor is a positive integer.
• Talking about the maximum value of the divisor we can trim it to the maximum value in the nums array because values greater than this will also always give the same answer.

• Now we have the minimum and the maximum value of divisor in our hand. Now our only task is to find the smallest divisor.
• We can manually check for each value in the [min, max] range but as the values in the range are sorted so we will use a Binary search algorithm for better time complexity.
• We are trying to find out the smallest value of the divisor so the loop will end when start<=end. In the end, the start will contain the final answer so we will return its value.

Code

C++ code for Find the Smallest Divisor Given a Threshold Leetcode Solution

#include <bits/stdc++.h> 
using namespace std; 
   int smallestDivisor(vector<int>& nums, int threshold) {
        int s=1,e=*max_element(nums.begin(),nums.end());
        int n=nums.size();
        while(s<=e)
        {
            int mid=s+(e-s)/2;
            int sum=0;
            for(int i=0;i<n;i++)
                sum=sum+(nums[i]+mid-1)/mid;
            if(sum<=threshold)
            {
                e=mid-1;
            }
            else
            {
                s=mid+1;
            }
                
        }
        return s;
    }

int main() 
{ 
 vector<int> arr = {1,2,5,9}; 
 int threshold = 6;
 cout<<smallestDivisor(arr,threshold)<<endl; 
 return 0;
}

5

Java code for Find the Smallest Divisor Given a Threshold Leetcode Solution

import java.util.Arrays; 
public class Tutorialcup {
 public static  int smallestDivisor(int[]  nums, int threshold) {
        int s=1,e=Arrays.stream(nums).max().getAsInt();
        int n=nums.length;
        while(s<=e)
        {
            int mid=s+(e-s)/2;
            int sum=0;
            for(int i=0;i<n;i++)
                sum=sum+(nums[i]+mid-1)/mid;
            if(sum<=threshold)
            {
                e=mid-1;
            }
            else
            {
                s=mid+1;
            }
                
        }
        return s;
    }

  public static void main(String[] args) {
    int [] arr = {1,2,5,9}; 
    int threshold = 6;
    int ans=  smallestDivisor(arr,threshold);
    System.out.println(ans);
  }
}

5

Complexity Analysis of Find the Smallest Divisor Given a Threshold Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the nums array only once. Here n is the length of the nums array.

Space complexity

O(1) because we using memory only to store the answer.

References