All problems

Find the Smallest Divisor Given a Threshold

Medium · binary search

You are given a list of positive integers nums and a number threshold.

Pick a positive integer d. Divide every number in nums by d, round each result up to the next whole number, and add the rounded results together. A bigger d makes the total smaller (or keeps it the same).

Return the smallest d for which the total is at most threshold. An answer always exists.

Examples

Example 1

Input: nums = [7, 12, 5, 9], threshold = 6

Output: 7

With d = 7 the rounded quotients are 1, 2, 1, 2, which add up to 6. With d = 6 they are 2, 2, 1, 2, which add up to 7, so 6 is too small.

Example 2

Input: nums = [10, 10, 10], threshold = 3

Output: 10

Every number must round to exactly 1, so d has to be at least 10.

Example 3

Input: nums = [4, 9, 2], threshold = 100

Output: 1

Even d = 1 gives a total of 15, which is already within the threshold.

Constraints