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.

  1. Determine the lower bound - The minimum possible divisor (low) is 1.
  2. Determine the upper bound - The maximum possible divisor (high) is the maximum value in the nums array because dividing each number by the maximum value will give the smallest possible result. high = 9
  3. 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 it canDivide.

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), where M is max element in the array, and n is length of array nums. We run log M iterations, and each iteration involves evaluating the canDivide function, which takes O(n) time, where n is the number of elements in nums.
  • Space: O(1)