Skip to main content
Talentd

Find the Smallest Divisor Given a Threshold - Solution & Explanation

MediumArrayBinary Search20 min readAsked at: Amazon, Microsoft, Meta +9
Practice this problem

Problem Statement

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 * 104
  • 1 <= nums[i] <= 106
  • nums.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.

The code uses binary search to find the smallest divisor. The loop continues until 'left' and 'right' converge. For each middle value, we compute the sum of divisions rounded up (utilizing integer arithmetic for efficiency), and adjust the search range based on whether this sum is more or less than the threshold.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space.

Try this approach in the editor →

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.

This code initiates a loop to test each divisor starting from 1 upwards until it finds the smallest divisor satisfying the condition. The ceiling of division is calculated with the same integer math trick as before.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1).

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Binary Search

Time Complexity: O(n * log(max(nums))) where n is the number of elements in nums. Space Complexity: O(1) as we use constant additional space.

Approach 2: Linear Scan with Improved Accuracy

Time Complexity: Potentially O(n * max(nums)). Space Complexity: O(1).

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Scan with Improved AccuracyO(n * m)O(1)Good for understanding the brute-force behavior or when max(nums) is very small
Binary Search on DivisorO(n log m)O(1)Best general solution when the divisor range is large and performance matters

Video Solution

BS-14. Find the Smallest Divisor Given a Threshold | Binary Search • take U forward • 218,587 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Find the Smallest Divisor Given a Threshold with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimized Maximum of Products Distributed to Any Store