{x}
blog image

Find the Smallest Divisor Given a Threshold

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division's result. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

The test cases are generated so that there will be an answer.

 

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 106
  • nums.length <= threshold <= 106

Solution Explanation: Find the Smallest Divisor Given a Threshold

This problem asks to find the smallest divisor such that the sum of the ceiling divisions of all numbers in an array by this divisor is less than or equal to a given threshold. The key insight is that this problem exhibits monotonicity: if a divisor d satisfies the condition, then any divisor greater than d will also satisfy it. This allows us to use binary search for an efficient solution.

Algorithm:

  1. Initialization:

    • Set the lower bound l to 1 (the smallest possible divisor).
    • Set the upper bound r to the maximum value in the input array nums. This is the largest possible divisor that needs to be considered because any larger divisor will result in a sum less than or equal to the sum when dividing by the maximum.

  2. Binary Search:

    • While l is less than r:
      • Calculate the middle value mid as (l + r) / 2.
      • Iterate through the nums array. For each number x, compute the ceiling division (x + mid - 1) / mid and add it to the running sum s.
      • If s is less than or equal to the threshold, it means mid is a potential solution. Update the upper bound r to mid to search for a smaller divisor.
      • Otherwise, mid is too small. Update the lower bound l to mid + 1.

  3. Return:

    • After the binary search loop, l will hold the smallest divisor that satisfies the condition. Return l.

Time Complexity Analysis:

  • The binary search takes O(log M) iterations, where M is the maximum value in nums.
  • In each iteration, we iterate through the nums array once, taking O(n) time, where n is the length of nums.
  • Therefore, the overall time complexity is O(n log M).

Space Complexity Analysis:

  • The algorithm uses a constant amount of extra space to store variables like l, r, mid, and s.
  • Therefore, the space complexity is O(1).

Code Examples:

The provided code demonstrates the solution in multiple programming languages. They all follow the same algorithmic structure described above:

Python (using bisect_left for efficiency):

import bisect
 
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int:
        def check(divisor):
            return sum((num + divisor - 1) // divisor for num in nums) <= threshold
 
        return bisect_left(range(max(nums) + 1), True, key=check)

This Python solution uses bisect_left from the bisect module, providing a more concise and potentially optimized binary search implementation.

The other language examples (Java, C++, Go, TypeScript, Rust, Javascript, C#) directly implement the binary search loop as described in the algorithm section. They all have the same time and space complexity.