LeetCode 1283 - Find the Smallest Divisor Given a Threshold

The problem asks us to find the smallest positive integer divisor for a given array nums such that when each element of

leetcodemediumarraybinary-search

LeetCode Problem 1283

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to find the smallest positive integer divisor for a given array nums such that when each element of the array is divided by this divisor, the sum of the ceiling of these divisions does not exceed a given threshold. In other words, for each num in nums, we compute ceil(num / divisor), sum these results, and ensure the sum is less than or equal to threshold. Our goal is to minimize divisor.

The input consists of an array of integers nums and an integer threshold. Each element in nums is between 1 and 10^6, and the length of nums can be up to 5 * 10^4. The threshold is at least as large as the array length and can go up to 10^6. This means a naive approach that tries every possible divisor could be too slow, especially since divisors could range from 1 to max(nums).

Edge cases include a threshold equal to the length of nums (forcing the divisor to be very large to reduce all divisions to 1) and arrays with all identical elements. The problem guarantees that there is always a solution, so we do not need to handle cases with no valid divisor.

Approaches

The brute-force approach would be to try every possible divisor starting from 1 up to max(nums). For each divisor, we compute the sum of the ceiling of the divisions. The first divisor where the sum is less than or equal to threshold is our answer. While correct, this approach is too slow for large inputs because it could require O(max(nums) * n) operations.

The optimal approach leverages binary search. The key insight is that the sum of ceiling divisions is a monotonically decreasing function of the divisor: as the divisor increases, the sum decreases. This allows us to efficiently search for the smallest divisor using binary search between 1 and max(nums). At each step, we compute the sum for the middle divisor and adjust our search range accordingly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * max(nums)) O(1) Check each divisor from 1 to max(nums)
Optimal O(n * log(max(nums))) O(1) Binary search on divisor using monotonicity

Algorithm Walkthrough

  1. Identify the search range. The smallest possible divisor is 1, and the largest is max(nums).

  2. Define a helper function to compute the sum of ceiling divisions for a given divisor. For each element num in nums, compute ceil(num / divisor), which can be implemented as (num + divisor - 1) // divisor to avoid floating-point operations.

  3. Perform binary search:

  4. Compute the midpoint mid of the current range.

  5. Compute the sum of ceiling divisions using the helper function.

  6. If the sum exceeds threshold, it means the divisor is too small. Set the new lower bound to mid + 1.

  7. If the sum is within threshold, it means the divisor may be valid, but there could be a smaller valid divisor. Set the new upper bound to mid - 1 and record mid as a candidate answer.

  8. Continue until the search range converges.

  9. Return the smallest divisor found.

Why it works: The monotonic property of the sum function ensures that once a divisor produces a sum within the threshold, all larger divisors will also satisfy the threshold. Binary search guarantees that we find the minimum such divisor efficiently.

Python Solution

from typing import List

class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def compute_sum(divisor: int) -> int:
            return sum((num + divisor - 1) // divisor for num in nums)

        left, right = 1, max(nums)
        result = right

        while left <= right:
            mid = (left + right) // 2
            if compute_sum(mid) <= threshold:
                result = mid
                right = mid - 1
            else:
                left = mid + 1

        return result

The helper function compute_sum computes the ceiling division sum efficiently using integer arithmetic. Binary search adjusts the search range based on whether the current mid satisfies the threshold. The variable result keeps track of the smallest valid divisor found.

Go Solution

func smallestDivisor(nums []int, threshold int) int {
    computeSum := func(divisor int) int {
        sum := 0
        for _, num := range nums {
            sum += (num + divisor - 1) / divisor
        }
        return sum
    }

    left, right := 1, 0
    for _, num := range nums {
        if num > right {
            right = num
        }
    }
    result := right

    for left <= right {
        mid := (left + right) / 2
        if computeSum(mid) <= threshold {
            result = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return result
}

In Go, we define a closure computeSum to compute the ceiling division sum. We also handle the computation of max(nums) manually. The binary search logic mirrors the Python version, ensuring minimal differences in behavior.

Worked Examples

Example 1: nums = [1,2,5,9], threshold = 6

divisor sum of ceilings comparison with threshold
1 1+2+5+9=17 17 > 6
2 1+1+3+5=10 10 > 6
3 1+1+2+3=7 7 > 6
4 1+1+2+3=7 7 > 6
5 1+1+1+2=5 5 <= 6

The smallest divisor satisfying the threshold is 5.

Example 2: nums = [44,22,33,11,1], threshold = 5

divisor sum of ceilings
44 1+1+1+1+1=5
43 2+1+1+1+1=6

The smallest divisor satisfying the threshold is 44.

Complexity Analysis

Measure Complexity Explanation
Time O(n * log(max(nums))) Each binary search step requires O(n) to compute the sum. The number of steps is O(log(max(nums))).
Space O(1) Only constant extra space is used, no additional data structures are needed.

Binary search efficiently narrows the divisor range, and the ceiling sum computation is linear in array size. The space remains constant because no recursion or auxiliary structures are used.

Test Cases

# Provided examples
assert Solution().smallestDivisor([1,2,5,9], 6) == 5  # Example 1
assert Solution().smallestDivisor([44,22,33,11,1], 5) == 44  # Example 2

# Edge cases
assert Solution().smallestDivisor([1], 1) == 1  # Single element, threshold=1
assert Solution().smallestDivisor([1,1,1,1], 4) == 1  # Threshold equals array length
assert Solution().smallestDivisor([1000000], 1) == 1000000  # Max single element
assert Solution().smallestDivisor([1,2,3,4,5], 15) == 1  # Threshold larger than sum
assert Solution().smallestDivisor([10,10,10,10], 4) == 10  # Threshold equals length
Test Why
[1,2,5,9], 6 Normal case with mixed numbers
[44,22,33,11,1], 5 Large numbers, small threshold
[1], 1 Minimal array and threshold
[1,1,1,1], 4 Threshold equals array length
[1000000], 1 Large single number
[1,2,3,4,5], 15 Threshold larger than total sum
[10,10,10,10], 4 Each element must be reduced to 1

Edge Cases

  1. Single-element array: When nums contains only one element, the smallest divisor is either 1 or the element itself depending on threshold. The implementation handles it naturally through binary search.
  2. Threshold equals array length: If threshold == len(nums), every division must result in 1 after ceiling, forcing the divisor to be at least max(nums). The binary search efficiently finds this.
  3. Large numbers: Arrays containing elements up to 10^6 require careful integer arithmetic to avoid floating-point errors. The use of (num + divisor - 1) // divisor ensures accurate ceiling division using integers.

This solution efficiently handles all edge cases and guarantees correctness by leveraging the monotonic property of the sum function with binary search.