> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/1283.-find-the-smallest-divisor-given-a-threshold.md).

# 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.<br>

## Complexity

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

## Code

```java
// 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;
}

```