Skip to content

1283.find-the-smallest-divisor-given-a-threshold.md

Latest commit

 

History

History
72 lines (59 loc) · 3.37 KB

1283.find-the-smallest-divisor-given-a-threshold.md

File metadata and controls

72 lines (59 loc) · 3.37 KB

1283. Find the Smallest Divisor Given a Threshold

Hints

  • What happens to the sum if you increase the divisor? Try a few examples.
  • Can you check if a given divisor is feasible in O(n)?

Key Insights

The core intuition is to recognize that as the divisor increases, the sum of all ceil(num / divisor) strictly decreases. This is because dividing by a larger number always produces a smaller (or equal) result for each element, and rounding up preserves this monotonicity. This monotonic relationship is the key to applying binary search.

How do we observe this?

  • Try a few divisors by hand from linear search: for small divisors, the sum is large; for large divisors, the sum is small.
  • For example, with nums = [1,2,5,9] and threshold = 6,
    • divisor = 1: sum = 17
    • divisor = 4: sum = 7
    • divisor = 5: sum = 5
    • As divisor increases, sum decreases.

How do we analyze the feasibility?

  • For any fixed divisor, we can check in O(n) if the sum of all ceil(num / divisor) is <= threshold.
  • If a divisor is feasible (sum <= threshold), then any larger divisor will also be feasible (sum will be even smaller).
  • If a divisor is not feasible, any smaller divisor will also not be feasible (sum will be even larger).

Summary:

  • When you see a problem where increasing a parameter makes a condition easier/harder in a predictable way, and you can check feasibility efficiently, consider binary search on that parameter.
  • Here, the divisor is the parameter, and the sum is monotonic with respect to it, so binary search is the optimal approach.

Binary Search

Use binary search to find the smallest divisor such that the sum of all ceil(num / divisor) is <= threshold.

  • Monotonicity: divisor is greater, sum is less <= threshold, more feasible.
  • Lower bound: 1, smallest possible divisor.
  • Upper bound: max(nums), the number can divide all numbers into 1 (the sum is the sum of all numbers).
  • Feasibility: For a given divisor, is the sum of all ceil(num / divisor) <= threshold?

For the check, you can use integer math: ceil(num / divisor) is equivalent to (num + divisor - 1) / divisor.

fun smallestDivisor(nums: IntArray, threshold: Int): Int {
    var left = 1
    var right = nums.max()
    while (left <= right) {
        val middle = left + (right - left) / 2
        val feasible = check(nums, threshold, middle)
        if (feasible) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

private fun check(nums: IntArray, threshold: Int, divisor: Int): Boolean {
    var sum = 0
    for (num in nums) {
        sum += ceil(num * 1f / divisor * 1f).toInt()
    }
    return sum <= threshold
}
  • Time Complexity: O(n * log m), where n is the length of nums, m is the maximum value in nums.
  • Space Complexity: O(1).

Edge Cases & Pitfalls

  • nums contains only one element: The answer is ceil(nums[0] / threshold).
  • threshold is equal to nums.size: The answer is max(nums).
  • All elements in nums are the same: The answer is ceil(nums[0] * nums.size / threshold).
  • Large values: Make sure to avoid integer overflow in the sum calculation.

Pitfalls

  • Forgetting to use integer math for ceil(num / divisor), which can lead to floating-point errors or inefficiency.