Problem
Given an array of integers nums
and an integer threshold
, we will choose a positive integer divisor
, divide all the array by it, and sum the division’s result. Find the smallest divisor
such that the result mentioned above is less than or equal to threshold
.
Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3
and 10/2 = 5
).
The test cases are generated so that there will be an answer.
Examples
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 of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
Example 2:
Input:
nums = [44,22,33,11,1], threshold = 5
Output:
44
Solution
Method 1 - Binary Search
To solve this problem, we can use a binary search approach to find the smallest divisor. Lets take eg. 1 nums = [1,2,5,9], threshold = 6
, and apply the algorithm.
- Determine the lower bound - The minimum possible divisor (
low
) is1
. - Determine the upper bound - The maximum possible divisor (
high
) is the maximum value in thenums
array because dividing each number by the maximum value will give the smallest possible result.high = 9
- Binary search the lower and upper bound, and see if we can divide the numbers such that sum of division is less than or equal to
threshold
. Lets call itcanDivide
.
Binary Search Iterations
Iteration 1
nums = [1,2,5,9], threshold = 6
low = 1, high = 9 => mid = (1 + 9) / 2 = 5
Check if divisor = 5 can result in a sum ≤ 6
sum = 1 + 1 + 1 + 2 = 5 (≤ threshold)
Can we find smaller divisor? Update `high = mid = 5`
Iteration 2
nums = [1,2,5,9], threshold = 6
low = 1, high = 5 => mid = (1 + 5) / 2 = 3
Check if divisor = 3 can result in a sum ≤ 6
sum = 1 + 1 + 2 + 3 = 7 (> threshold)
Can we find bigger divisor? Update `low = mid + 1 = 4`
Iteration 3
nums = [1,2,5,9], threshold = 6
low = 4, high = 5 => mid = (4 + 5) / 2 = 4
Check if divisor = 4 can result in a sum ≤ 6
sum = 1 + 1 + 2 + 3 = 7 (> threshold)
Can we find bigger divisor? Update `low = mid + 1 = 5`
Iteration 4
nums = [1,2,5,9], threshold = 6
low = 5, high = 5
So, we break out. And low = high = 5
is our answer.
Code
Java
public class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int low = 1; // Minimum possible divisor
int high = Arrays.stream(nums).max().getAsInt(); // Maximum possible divisor
while (low < high) {
int mid = low + (high - low) / 2;
if (canDivide(nums, threshold, mid)) {
high = mid; // Try smaller divisor
} else {
low = mid + 1; // Increase the divisor
}
}
return low; // or high, since they will converge
}
private boolean canDivide(int[] nums, int threshold, int divisor) {
int sum = 0;
for (int num: nums) {
sum += (num + divisor - 1) / divisor; // Equivalent to Math.ceil((double) num / divisor)
if (sum > threshold) {
return false; // Exceeded threshold
}
}
return true; // Sum is within threshold
}
}
Complexity
- Time:
O(log M * n)
, whereM
is max element in the array, andn
is length of arraynums
. We runlog M
iterations, and each iteration involves evaluating thecanDivide
function, which takes O(n) time, wheren
is the number of elements innums
. - Space:
O(1)