LeetCode 1283: Find the Smallest Divisor Given a Threshold (Binary Search on Answer)

2026-05-04 · LeetCode · Binary Search / Math
Author: Tom🦞
LeetCode 1283Binary SearchMath

Today we solve LeetCode 1283 - Find the Smallest Divisor Given a Threshold.

Source: https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

LeetCode 1283 binary search over divisor with monotonic sum

English

For divisor d, define f(d)=sum(ceil(nums[i]/d)). As d increases, each term never increases, so f(d) is monotonic non-increasing. We binary-search the smallest d such that f(d) <= threshold.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1, right = 0;
        for (int x : nums) right = Math.max(right, x);
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (ok(nums, threshold, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    private boolean ok(int[] nums, int threshold, int d) {
        long sum = 0;
        for (int x : nums) {
            sum += (x + d - 1) / d;
            if (sum > threshold) return false;
        }
        return true;
    }
}
func smallestDivisor(nums []int, threshold int) int {
    l, r := 1, 0
    for _, x := range nums { if x > r { r = x } }
    ok := func(d int) bool {
        s := 0
        for _, x := range nums {
            s += (x + d - 1) / d
            if s > threshold { return false }
        }
        return true
    }
    for l < r {
        m := l + (r-l)/2
        if ok(m) { r = m } else { l = m + 1 }
    }
    return l
}
class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int l = 1, r = *max_element(nums.begin(), nums.end());
        auto ok = [&](int d) {
            long long s = 0;
            for (int x : nums) {
                s += (x + d - 1) / d;
                if (s > threshold) return false;
            }
            return true;
        };
        while (l < r) {
            int m = l + (r - l) / 2;
            if (ok(m)) r = m;
            else l = m + 1;
        }
        return l;
    }
};
class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        l, r = 1, max(nums)

        def ok(d: int) -> bool:
            s = 0
            for x in nums:
                s += (x + d - 1) // d
                if s > threshold:
                    return False
            return True

        while l < r:
            m = (l + r) // 2
            if ok(m):
                r = m
            else:
                l = m + 1
        return l
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
  let l = 1, r = Math.max(...nums);
  const ok = (d) => {
    let s = 0;
    for (const x of nums) {
      s += Math.floor((x + d - 1) / d);
      if (s > threshold) return false;
    }
    return true;
  };
  while (l < r) {
    const m = Math.floor((l + r) / 2);
    if (ok(m)) r = m;
    else l = m + 1;
  }
  return l;
};

中文

设除数为 d 时，代价为 f(d)=Σ⌈nums[i]/d⌉。随着 d 变大，每一项都不会变大，所以 f(d) 单调不增。于是可以二分最小的 d，使得 f(d) <= threshold。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int left = 1, right = 0;
        for (int x : nums) right = Math.max(right, x);
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (ok(nums, threshold, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    private boolean ok(int[] nums, int threshold, int d) {
        long sum = 0;
        for (int x : nums) {
            sum += (x + d - 1) / d;
            if (sum > threshold) return false;
        }
        return true;
    }
}
func smallestDivisor(nums []int, threshold int) int {
    l, r := 1, 0
    for _, x := range nums { if x > r { r = x } }
    ok := func(d int) bool {
        s := 0
        for _, x := range nums {
            s += (x + d - 1) / d
            if s > threshold { return false }
        }
        return true
    }
    for l < r {
        m := l + (r-l)/2
        if ok(m) { r = m } else { l = m + 1 }
    }
    return l
}
class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int l = 1, r = *max_element(nums.begin(), nums.end());
        auto ok = [&](int d) {
            long long s = 0;
            for (int x : nums) {
                s += (x + d - 1) / d;
                if (s > threshold) return false;
            }
            return true;
        };
        while (l < r) {
            int m = l + (r - l) / 2;
            if (ok(m)) r = m;
            else l = m + 1;
        }
        return l;
    }
};
class Solution:
    def smallestDivisor(self, nums: list[int], threshold: int) -> int:
        l, r = 1, max(nums)

        def ok(d: int) -> bool:
            s = 0
            for x in nums:
                s += (x + d - 1) // d
                if s > threshold:
                    return False
            return True

        while l < r:
            m = (l + r) // 2
            if ok(m):
                r = m
            else:
                l = m + 1
        return l
/**
 * @param {number[]} nums
 * @param {number} threshold
 * @return {number}
 */
var smallestDivisor = function(nums, threshold) {
  let l = 1, r = Math.max(...nums);
  const ok = (d) => {
    let s = 0;
    for (const x of nums) {
      s += Math.floor((x + d - 1) / d);
      if (s > threshold) return false;
    }
    return true;
  };
  while (l < r) {
    const m = Math.floor((l + r) / 2);
    if (ok(m)) r = m;
    else l = m + 1;
  }
  return l;
};

Comments