FunctionRacerProblemsRace

Smallest Divisor Under a Limit

MediumSorting and searchingPython, JavaScript, TypeScript, Java, C++

Pick a positive integer d and divide every item of nums by it, rounding each result up to a whole number (so 7 / 2 counts as 4, and 6 / 3 as 2). Add up the rounded results. Return the smallest d for which this sum is at most limit.

All items are positive and limit is at least len(nums), so a large enough d always works (every item then rounds up to 1). A bigger d never makes the sum bigger, which makes binary search over d possible.

Example 1

nums [1,2,5,9]
limit 6
returns 5

With d = 5 the rounded results are 1, 1, 1, 2 (sum 5); with d = 4 they are 1, 1, 2, 3 (sum 7), which is too much.

Example 2

nums [2,3,5,7,11]
limit 11
returns 3

d = 3 gives 1 + 1 + 2 + 3 + 4 = 11, exactly the limit, while d = 2 gives 16.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Sorting and searching problems