Smallest Divisor Greater Than Threshold
Optimal Binary Search Approach

⬅ Previous Topic

Next Topic ⮕

Topic Contents

Problem Examples Solution Visualization Algorithm Code Time Space

Problem Statement

You are given a list of positive integers nums and a positive integer threshold. Your task is to find the smallest positive integer divisor such that the sum of all elements in the array when each is divided by this divisor (rounded up) is less than or equal to threshold.

For each number in the array, you must compute ceil(num / divisor).
The final sum of these values must not exceed the given threshold.

If nums is empty or threshold is not a valid positive number, return -1.

Examples❯

Input Array	Threshold	Smallest Divisor	Description
[1, 2, 5, 9]	6	5	Dividing with 5: ceil(1/5)+ceil(2/5)+ceil(5/5)+ceil(9/5) = 1+1+1+2 = 5 ≤ 6
[2, 3, 5, 7, 11]	11	3	Dividing with 3 gives total sum 9, which is ≤ threshold
[19]	5	4	We need to divide 19 so that ceil(19/divisor) ≤ 5
[1, 2, 3]	3	1	Any number divided by 1 will result in original value, sum = 6, so must search for larger divisor
[100, 200, 300]	3	300	Only a very large divisor can reduce the sum below threshold
[1]	1	1	Only one number, and we need sum ≤ 1, so divisor = 1
[]	5	-1	Empty array, nothing to divide
[1, 2, 3]	0	-1	Threshold is invalid (non-positive)

Solution❯

To solve this problem, we need to understand what it means to divide all numbers by a divisor and take the ceiling of each result. The goal is to find the smallest such divisor that keeps the sum of all these rounded-up divisions within the specified threshold.

Understanding the Problem

For example, if the array is [1, 2, 5, 9] and we divide each number by 5, we get:

ceil(1/5) = 1
ceil(2/5) = 1
ceil(5/5) = 1
ceil(9/5) = 2

So the sum is 1 + 1 + 1 + 2 = 5, which is within the threshold of 6. The challenge is to find the smallest such divisor that still keeps this sum within limits.

Different Situations to Consider

If the divisor is small (e.g., 1): Then each number is divided by 1, so the sum of the array stays the same (no reduction).
If the divisor is large (e.g., more than the max value in array): Then all divisions will round up to 1, which may help reduce the total sum.

The key is to find a balance — a divisor large enough to reduce the sum, but as small as possible.

What Happens in Edge Cases?

If the array is empty, we can't divide anything. So we return -1.
If the threshold is zero or negative, there's no way to achieve a valid result, so again return -1.

How Do We Search Efficiently?

Instead of checking each divisor one by one, we can use binary search from 1 to max(nums). For each candidate divisor, we calculate the sum of ceilings, and decide if we need a larger or smaller divisor. This drastically reduces the number of checks and makes it efficient.

At the end of this process, we’ll have the smallest divisor that satisfies the condition. If no such divisor is found (which happens only if input is invalid), we return -1.

This method ensures optimal performance and is suitable even when the input array is very large.

Visualization

Algorithm Steps

Initialize low = 1 and high = max(nums).
While low ≤ high:
→ Calculate mid as the potential divisor.
→ Compute sum = sum(ceil(num / mid) for num in nums).
→ If sum ≤ threshold: store mid as potential answer, and search for smaller divisor by setting high = mid - 1.
→ Else: search higher by setting low = mid + 1.
Return the smallest valid divisor found.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

import math

def smallestDivisor(nums, threshold):
    def compute_sum(divisor):
        return sum(math.ceil(num / divisor) for num in nums)

    low, high = 1, max(nums)
    answer = high

    while low <= high:
        mid = (low + high) // 2
        if compute_sum(mid) <= threshold:
            answer = mid        # Valid divisor, try smaller one
            high = mid - 1
        else:
            low = mid + 1       # Too large sum, increase divisor

    return answer

nums = [1, 2, 5, 9]
threshold = 6
print("Smallest Divisor:", smallestDivisor(nums, threshold))

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(n)	In each binary search step, computing the sum involves iterating through the entire array.
Average Case	O(n log m)	Binary search over range [1, max(nums)], and each step takes O(n) time to compute the sum.
Worst Case	O(n log m)	Same as average case — n elements, log(max(nums)) search steps.

Space Complexity

O(1)

Explanation: Only a few variables are used; no extra space proportional to input size.

⬅ Previous Topic

Minimum Days to Make M Bouquets

Next Topic ⮕

Capacity to Ship Packages within D Days

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Smallest Divisor Greater Than Threshold
Optimal Binary Search Approach

Problem Statement

Examples❯

Solution❯

Understanding the Problem

Different Situations to Consider

What Happens in Edge Cases?

How Do We Search Efficiently?

Visualization

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Smallest Divisor Greater Than ThresholdOptimal Binary Search Approach

Problem Statement

Examples❯

Solution❯

Understanding the Problem

Different Situations to Consider

What Happens in Edge Cases?

How Do We Search Efficiently?

Visualization

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Smallest Divisor Greater Than Threshold
Optimal Binary Search Approach