Find the Smallest Divisor Given a Threshold solution and explanation
IBM
Google
9 more videos on this problem
BS-14. Find the Smallest Divisor Given a Threshold | Binary Searchtake U forward · 16:00 · 218K views
Find the Smallest Divisor Given a Threshold | LeetCode 1283 | C++, Java, PythonKnowledge Center · 18:45 · 3K views
find the smallest divisor given a threshold leetcode | leetcode 1283 | binary searchNaresh Gupta · 10:26 · 3K views
Find the Smallest Divisor Given a Threshold | Live Coding with Explanation | Leetcode #1283Algorithms Made Easy · 6:52 · 2K views
花花酱 LeetCode 1283. Find the Smallest Divisor Given a Threshold - 刷题找工作 EP282Hua Hua · 10:12 · 2K views
Find the Smallest Divisor Given a Threshold | Leet code 1283 | Theory explained + Python codeSai Anish Malla · 10:22 · 1K views
Leetcode 1283: Find the Smallest Divisor Given a ThresholdAlgorithms Casts · 16:47 · 1K views
Find the Smallest Divisor Given a Threshold Leetcode | Leetcode 1283 | Leetcode november challengeCode Bashers · 10:09 · 986 views
LeetCode 1283. Find the Smallest Divisor Given a ThresholdHappy Coding · 9:41 · 736 views
Find The Smallest Divisor Given A Threshold - LeetCode SolutionPrepForTech with Pratik · 12:16 · 702 views
The 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 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).
Example 2:
Input: nums = [44,22,33,11,1], threshold = 5 Output: 44
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 106nums.length <= threshold <= 106
Approach overview
Problem Overview: You are given an integer array nums and a threshold. Choose a divisor such that every number in the array is divided by it, rounded up using ceil(num / divisor). The goal is to return the smallest divisor where the total sum of these rounded results does not exceed the threshold.
Approach 1: Linear Scan with Improved Accuracy (Time: O(n * m), Space: O(1))
The most direct strategy checks every possible divisor from 1 up to max(nums). For each candidate divisor, iterate through the array and compute ceil(num / divisor). Accumulate the values and stop early if the sum exceeds the threshold. The first divisor that keeps the sum within the threshold is the answer. This approach is simple and useful for understanding the constraint behavior, but it becomes slow when the maximum value in nums is large because every divisor candidate must be evaluated.
Approach 2: Binary Search on the Divisor (Time: O(n log m), Space: O(1))
The key observation: as the divisor increases, the total sum of ceil(num / divisor) monotonically decreases. Larger divisors produce smaller division results. This monotonic property allows you to apply binary search over the range [1, max(nums)]. For a mid divisor, iterate through the array and compute the total rounded division sum. If the sum is greater than the threshold, the divisor is too small, so move the search to the right. Otherwise, try smaller divisors on the left to minimize the answer. Each check costs O(n), and the search range halves every step, leading to O(n log m) time where m = max(nums).
Recommended for interviews: Binary search on the answer space is the expected solution. Interviewers look for the recognition that the result function is monotonic with respect to the divisor. A quick brute-force explanation shows you understand the problem, but implementing the O(n log m) binary search demonstrates algorithmic maturity and familiarity with search-space optimization patterns.
Approach 1: Approach 1: Binary Search
This approach uses binary search to efficiently find the smallest divisor. The possible divisors can range from 1 to the maximum number in the array. For each candidate divisor, divide each number in the array, take the ceiling of the division result, sum it up, and compare against the threshold.
Binary search helps minimize the number of trials by adjusting the divisor range based on whether the threshold condition is met or not for a given divisor.
import math
def smallestDivisor(nums, threshold):
left, right = 1, 1000000
while left < right:
mid = (left + right) // 2
sum_div = sum((num + mid - 1) // mid for num in nums)
if sum_div > threshold:
left = mid + 1
else:
right = mid
return leftpublic class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int left = 1, right = 1000000;
while (left < right) {
int mid = (left + right) / 2;
int sum = 0;
for (int num : nums) {
sum += (num + mid - 1) / mid;
}
if (sum > threshold) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int left = 1, right = 1000000;
while (left < right) {
int mid = (left + right) / 2;
int sum = 0;
for (int num : nums) {
sum += (num + mid - 1) / mid;
}
if (sum > threshold) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};function smallestDivisor(nums, threshold) {
let left = 1, right = 1000000;
while (left < right) {
let mid = Math.floor((left + right) / 2);
let sum = nums.reduce((acc, num) => acc + Math.ceil(num / mid), 0);
if (sum > threshold) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}#include <stdio.h>
#include <math.h>
int smallestDivisor(int* nums, int numsSize, int threshold) {
int left = 1, right = 1e6;
while (left < right) {
int mid = (left + right) / 2;
int sum = 0;
for (int i = 0; i < numsSize; ++i) {
sum += (nums[i] + mid - 1) / mid; // Equivalent to ceil(nums[i] / mid)
}
if (sum > threshold) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}public class Solution {
public int SmallestDivisor(int[] nums, int threshold) {
int left = 1, right = 1000000;
while (left < right) {
int mid = (left + right) / 2;
int sum = 0;
foreach (int num in nums) {
sum += (num + mid - 1) / mid;
}
if (sum > threshold) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}The Python solution uses list comprehension with the binary search strategy. By calculating the ceiling in a repetitive fashion using integer math, it efficiently narrows down the potential divisor range.
Time Complexity: O(n * log(max(nums))). Space Complexity: O(1).
Approach 2: Approach 2: Linear Scan with Improved Accuracy
This method involves a simple linear search from divisor = 1 upwards, incrementally checking each candidate as a divisor. This approach is less efficient compared to binary search but helps understand the problem in a straightforward manner. We calculate the total sum of the divisions for each divisor and stop when the sum is less or equal to the threshold. Ensuring progressively checking divisors until a valid one is found assures correctness.
def smallestDivisor(nums, threshold):
divisor = 1
while True:
if sum((num + divisor - 1) // divisor for num in nums) <= threshold:
return divisor
divisor += 1public class Solution {
public int smallestDivisor(int[] nums, int threshold) {
for (int divisor = 1; ; divisor++) {
int sum = 0;
for (int num : nums) {
sum += (num + divisor - 1) / divisor;
}
if (sum <= threshold) {
return divisor;
}
}
}
}#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
for (int divisor = 1; ; ++divisor) {
int sum = 0;
for (int num : nums) {
sum += (num + divisor - 1) / divisor;
}
if (sum <= threshold) {
return divisor;
}
}
}
};function smallestDivisor(nums, threshold) {
let divisor = 1;
while (true) {
const sum = nums.reduce((acc, num) => acc + Math.ceil(num / divisor), 0);
if (sum <= threshold) return divisor;
divisor++;
}
}#include <stdio.h>
#include <math.h>
int smallestDivisor(int* nums, int numsSize, int threshold) {
for (int divisor = 1; ; ++divisor) {
int sum = 0;
for (int i = 0; i < numsSize; ++i) {
sum += (nums[i] + divisor - 1) / divisor;
}
if (sum <= threshold) {
return divisor;
}
}
}public class Solution {
public int SmallestDivisor(int[] nums, int threshold) {
for (int divisor = 1; ; divisor++) {
int sum = 0;
foreach (int num in nums) {
sum += (num + divisor - 1) / divisor;
}
if (sum <= threshold) {
return divisor;
}
}
}
}The Python approach is a direct translation into Python's loop and list-comp behaviour, trying each divisor until the threshold condition is met, returning the smallest valid divisor found.
Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1).
Approach 3: Binary Search
Notice that for number v, if the sum of results of dividing each number in nums by v is less than or equal to threshold, then all values greater than v satisfy the condition. There is a monotonicity, so we can use binary search to find the smallest v that satisfies the condition.
We define the left boundary of the binary search l=1, r=max(nums). Each time we take mid=(l+r)/2, calculate the sum of the results of dividing each number in nums by mid s, if s is less than or equal to threshold, then it means that mid satisfies the condition, we will update r to mid, otherwise we will update l to mid+1.
Finally, return l.
The time complexity is O(n times log M), where n is the length of the array nums and M is the maximum value in the array nums. The space complexity is O(1).
function smallestDivisor(nums: number[], threshold: number): number {
let l = 1;
let r = Math.max(...nums);
while (l < r) {
const mid = (l + r) >> 1;
const s = nums.reduce((acc, x) => acc + Math.ceil(x / mid), 0);
if (s <= threshold) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}func smallestDivisor(nums []int, threshold int) int {
return sort.Search(slices.Max(nums), func(v int) bool {
v++
s := 0
for _, x := range nums {
s += (x + v - 1) / v
}
return s <= threshold
}) + 1
}impl Solution {
pub fn smallest_divisor(nums: Vec<i32>, threshold: i32) -> i32 {
let mut l = 1;
let mut r = *nums.iter().max().unwrap();
while l < r {
let mid = (l + r) / 2;
let s: i32 = nums.iter().map(|&x| (x + mid - 1) / mid).sum();
if s <= threshold {
r = mid;
} else {
l = mid + 1;
}
}
l
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search | Time Complexity: O(n * log(max(nums))). Space Complexity: O(1). |
| Approach 2: Linear Scan with Improved Accuracy | Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1). |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with Improved Accuracy | O(n * m) | O(1) | Good for understanding the brute-force behavior or when max(nums) is very small |
| Binary Search on Divisor | O(n log m) | O(1) | Best general solution when the divisor range is large and performance matters |
Frequently asked questions
Is Find the Smallest Divisor Given a Threshold easy or hard?
The problem is classified as Medium difficulty. The main challenge is recognizing the monotonic relationship between the divisor and the computed sum. Once that insight is clear, applying binary search makes the implementation straightforward.
Find the Smallest Divisor Given a Threshold Python/Java solution
Most implementations compute the sum using integer math like (num + divisor - 1) // divisor to simulate ceil division efficiently. The binary search loop adjusts left and right bounds until the smallest valid divisor is found. This pattern works consistently across Python, Java, C++, JavaScript, and C#.
How to solve Find the Smallest Divisor Given a Threshold in O(n log m)?
Use binary search over the divisor range [1, max(nums)]. For each candidate divisor, compute the sum of ceil(num / divisor) for all elements. If the sum exceeds the threshold, increase the divisor; otherwise search for a smaller valid divisor. This reduces the search space logarithmically while each evaluation scans the array once.
What is the best approach for Find the Smallest Divisor Given a Threshold?
Binary search on the divisor range is the optimal approach. The sum of ceil divisions decreases as the divisor increases, which creates a monotonic search space. By binary searching between 1 and max(nums), you can find the smallest valid divisor in O(n log m) time, where m is the maximum number in the array.
Is Find the Smallest Divisor Given a Threshold asked at Google/Amazon/Meta?
This problem follows a common interview pattern called binary search on the answer. Variants of this pattern frequently appear in interviews at companies like Amazon, Google, and Meta, especially when a monotonic condition allows narrowing the search range.
What data structure is used in Find the Smallest Divisor Given a Threshold?
The problem primarily uses an array for input storage and binary search logic over the numeric range of possible divisors. No additional data structures are required beyond a few variables for tracking the sum and search bounds, resulting in constant extra space.
What is the time complexity of Find the Smallest Divisor Given a Threshold?
The optimal solution runs in O(n log m) time. Each binary search step checks a candidate divisor by iterating through the array in O(n). The divisor range from 1 to max(nums) contributes the log m factor. Space complexity is O(1).