Get started

Find the Smallest Divisor Given a Threshold — Medium Problem & Solution

Pick a positive integer divisor, divide every element of nums by it, round each result up, and sum them.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Pick a positive integer divisor, divide every element of nums by it, round each result up, and sum them.

Return the smallest divisor whose sum is at most threshold.

Example 1

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: Dividing by 5 gives 1 + 1 + 1 + 2 = 5; dividing by 4 gives 7, which is too big.

Example 2

Input: nums = [44,22,33,11,1], threshold = 5
Output: 44

Example 3

Input: nums = [21212,10101,12121], threshold = 1000000
Output: 1

Constraints

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 1000000
  • nums.length <= threshold <= 1000000

How to solve Find the Smallest Divisor Given a Threshold

The sum of the rounded-up quotients is non-increasing in the divisor, so binary search the smallest divisor whose sum fits under the threshold.

Approach

  1. Search d over [1, max(nums)] — anything larger makes every term 1, the same as max(nums).
  2. total(d): sum ceil(nums[i] / d), written as (nums[i] + d - 1) / d in integers.
  3. Return the smallest d with total(d) <= threshold.

Why it works

ceil(x / d) is non-increasing in d for fixed positive x, so the sum is too — the predicate flips exactly once. The guarantee threshold >= nums.length means the answer always exists, since d = max(nums) makes every term 1 and the sum equal to the array's length.

Complexity

  • Time — O(n log M) where M is the largest element
  • Space — O(1)

Pitfalls

  • Floating-point Math.ceil(x / d) loses precision for large values; use the integer form.
  • The search starts at 1 — a divisor of 0 is undefined.
  • The sum reaches about 5 · 10^4 · 10^6 for d = 1, so it needs 64-bit or an early exit.

Reference solution

Python

from typing import List

def smallestDivisor(nums: List[int], threshold: int) -> int:
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        total = sum((x + mid - 1) // mid for x in nums)
        if total <= threshold:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var smallestDivisor = function(nums, threshold) {
    var lo = 1, hi = nums[0], i;
    for (i = 1; i < nums.length; i++) if (nums[i] > hi) hi = nums[i];
    var total = function(d) {
        var s = 0;
        for (var j = 0; j < nums.length; j++) s += Math.floor((nums[j] + d - 1) / d);
        return s;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (total(mid) <= threshold) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue