You are given an array of integers nums and an integer K, your task is to find the smallest positive integer divisor, such that upon dividing all the elements of the given array by it, the sum of the division's result is less than or equal to the given integer K.
Each result of the division is rounded to the nearest integer greater than or equal to that element. For Example: 7/3 = 3.
Example:
Input:
A = [1 2 5 9]
6
Output:
5
Explanation:
If the divisor is 5 the sum will be 5 (1+1+1+2), which is less than 6.
Your Task:
Complete the function int smallestDivisor(), which takes a vector nums and an integer K and returns the smallest integer as asked.
Expected Time Complexity: O(nlogn).
Expected Auxiliary Space: O(n).
Constraints:
1 <= nums.length <= 5 * 10^{5}
1 <= nums[i] <= 10^{9}
nums.length <= K <= 10^{6}

见题面

见题面