1283. Find the Smallest Divisor Given a Threshold

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

 

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

 

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^6
• nums.length <= threshold <= 10^6

divisor 값을 1씩 증가켜서 찾다보면 시간 복잡도는 O(10^10) 이 나오게 된다.

 

이 시간을 줄이기 위해서는 divisor 값의 탐색 시간을 줄여야 하는데 binary search 를 통해서 탐색 시간을 줄일 수가 있다.

 

위의 예제에 있는 [1, 2, 5, 9] 를 예로 들어보면, divisor 에 따른 threshold 값은 아래 그림과 같다.

즉, 문제를 바꿔 말하면 6보다 작은 threshold 값 중에 가장 큰 값을 가지는 divisor 를 찾는 문제이다.

 

 

public class FindTheSmallestDivisorGivenAThreshold {

    public static void main(String[] args) {
        int [] nums = {1,2,3};
        int threshold = 6;

        FindTheSmallestDivisorGivenAThreshold ftsdgat = new FindTheSmallestDivisorGivenAThreshold();
        System.out.println(ftsdgat.smallestDivisor(nums, threshold));
    }

    public int smallestDivisor(int[] nums, int threshold) {
        return solve(nums, threshold, 0, (int)1e6);
    }

    int solve(int [] nums, int threshold, int left, int right) {
        if (left < right) {
            int m = (left + right) / 2;

            int sum1 = getSum(nums, m);
            int sum2 = getSum(nums, m+1);

            if (sum1 > threshold && sum2 <= threshold) {
                return m+1;
            }

            if (sum1 <= threshold) {
                return solve(nums, threshold, left, m);
            } else {
                return solve(nums, threshold, m+1, right);
            }
        }

        return 0;
    }

    int getSum(int [] nums, int divisor) {
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += Math.ceil((double)nums[i] / (double)divisor);
        }

        return sum;
    }
}