484. Find the Smallest Divisor Given a Threshold

Given an array and a threshold, choose a positive integer divisor and divide every element by it, rounding each result up to the nearest integer, then sum these. Return the smallest divisor such that this sum is less than or equal to the threshold. Input: '[arr], threshold'.

Input: '[arr], threshold'.

Output: Integer — the smallest valid divisor.

Examples

Input: [1,2,5,9], 6
Output: 5
Explanation: Divisor 5 gives sum 1+1+1+2=5<=6.

Input: [44,22,33,11,1], 5
Output: 44
Explanation: Large divisor needed.

Input: [2,3,5,7,11], 11
Output: 3
Explanation: Smallest divisor with sum<=11.

Constraints

• 1<=n<=5*10^4
• 1<=value<=10^6
• n<=threshold<=10^6

Asked by