Find the Smallest Divisor Given a Threshold

IF
AlgoAxiomStaff Engineers
JSTS
Medium20 mins

Given an array of integers nums and an integer threshold, find the smallest divisor such that the result of dividing all elements by the divisor (rounded up) and summing them 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 (i.e., Math.ceil).

Examples

Example 1:

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

Output: 5

Explanation: With divisor 5: ceil(1/5) + ceil(2/5) + ceil(5/5) + ceil(9/5) = 1 + 1 + 1 + 2 = 5 ≤ 6.

Example 2:

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

Output: 44

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^6
  • nums.length <= threshold <= 10^6
Source: Modified Binary Search pattern — AlgoAxiom
JavaScript
Test Case 1
root = [1, 2, 3]
Test Case 2
root = [1, 2, 3, 4, 5]
Idle