Smallest Divisor Under a Limit

Medium

You are given an array of positive integers amounts and an integer limit. Pick an integer divisor d ≥ 1, divide every number in the array by it rounding **up** (so 7 / 3 gives 3 and 10 / 2 gives 5), and add up the results. Find the smallest d for which this sum is at most limit. The value of limit is guaranteed to be at least the array length, so a suitable divisor always exists.

Example 1

amounts=[3, 8, 14], limit=5 → 7

With divisor 6 the sum is 1 + 2 + 3 = 6, which exceeds 5. With divisor 7 it is 1 + 2 + 2 = 5, which fits.

Example 2

amounts=[6, 6], limit=12 → 1

Divisor 1 already gives a sum of 12, and no divisor is smaller.

Constraints

1 ≤ len(amounts) ≤ 5·10⁴
1 ≤ amounts[i] ≤ 10⁶
len(amounts) ≤ limit ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

Find in a Shifted Sorted Array Medium First and Last Copy Medium Find in a Row-Chained Grid Medium Find in a Shifted Array With Repeats Medium Minimum of a Shifted List Medium

Input

amounts=[3, 8, 14], limit=5

Expected

Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.