Company: Agoda
Difficulty: medium
Minimum Divisor Given an array of integers, each element is to be divided by an integer so that the sum of the results is less than or equal to a threshold. Each non-integer result of division is rounded up before it is added to the sum. For example, 1/2 = 0.111... it is rounded up to 1. Determine the minimum divisor to make the sum less than or equal to the threshold. Parameters int arr[] : an array of integers int threshold : the maximum value of the sum Returns int : the minimum divisor Constraints 1 ≤ n ≤ 10 5 n ≤ threshold ≤ 10 9 1 ≤ arr[i] ≤ 10 9 , 0 ≤ i Sample Case 0 Input: arr[] size n = 3 arr = [2, 4, 5] threshold = 10 Output: 2 Explanation: The sum of the original array is 13 which is greater than the threshold 10. Test a divisor 2 which is higher than the divisor 1: arr' = [1, 2, 3] which sums to 6 ≤ 10. The minimum divisor to make the sum less than or equal to the threshold is 2. Sample Case 1 Input: arr[] size n = 4 arr = [30069534, 82705253] threshold = 82705253 Output: 1