1283. Find the Smallest Divisor Given a Threshold LeetCode Solution
In this guide, you will get 1283. Find the Smallest Divisor Given a Threshold LeetCode Solution with the best time and space complexity. The solution to Find the Smallest Divisor Given a Threshold problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Smallest Divisor Given a Threshold
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 smallest divisor 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).
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).
1283. Find the Smallest Divisor Given a Threshold LeetCode Solution in C++
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int l = 1;
int r = ranges::max(nums);
while (l < r) {
const int m = (l + r) / 2;
if (sumDivision(nums, m) <= threshold)
r = m;
else
l = m + 1;
}
return l;
}
private:
int sumDivision(const vector<int>& nums, int m) {
int sum = 0;
for (const int num : nums)
sum += (num - 1) / m + 1;
return sum;
}
}; /* code provided by PROGIEZ */
1283. Find the Smallest Divisor Given a Threshold LeetCode Solution in Java
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int l = 1;
int r = Arrays.stream(nums).max().getAsInt();
while (l < r) {
final int m = (l + r) / 2;
if (sumDivision(nums, m) <= threshold)
r = m;
else
l = m + 1;
}
return l;
}
private int sumDivision(int[] nums, int m) {
int sum = 0;
for (final int num : nums)
sum += (num - 1) / m + 1;
return sum;
}
} // code provided by PROGIEZ
1283. Find the Smallest Divisor Given a Threshold LeetCode Solution in Python
class Solution:
def smallestDivisor(self, nums: list[int], threshold: int) -> int:
l = 1
r = max(nums)
while l < r:
m = (l + r) // 2
if sum((num - 1) // m + 1 for num in nums) <= threshold:
r = m
else:
l = m + 1
return l # code by PROGIEZ
