1283. Find the Smallest Divisor Given a Threshold

Intuition

We are asked to find the smallest divisor such that the sum of the division results (rounded up) of all elements in the array is less than or equal to a threshold.

As the divisor increases, the division results decrease, hence the total sum decreases. This property makes the problem monotonic, so we can use binary search to find the smallest valid divisor.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N*\log{N})$

Code

// Helper function to calculate the total sum of ceil(num / divisor) for all elements
int calculateSum(int[] numbers, int divisor) {
    int total = 0;
    for (int number : numbers) {
        // Use Math.ceil to ensure we round up the division
        total += Math.ceil(1.0 * number / divisor);
    }
    return total;
}

public int smallestDivisor(int[] numbers, int threshold) {
    int left = 1;
    int right = 1;
    int smallestValidDivisor = 0;

    // Determine the upper bound for binary search (max number in array)
    for (int number : numbers) {
        right = Math.max(right, number);
    }

    // Edge case: all elements are the same
    if (left == right) return left;

    // Binary search for the smallest valid divisor
    while (left <= right) {
        int midDivisor = (left + right) / 2;
        int currentSum = calculateSum(numbers, midDivisor);

        if (currentSum <= threshold) {
            // Current divisor is valid; try to minimize it
            smallestValidDivisor = midDivisor;
            right = midDivisor - 1;
        } else {
            // Too large a sum, need a bigger divisor
            left = midDivisor + 1;
        }
    }

    return smallestValidDivisor;
}