# Find the Smallest Divisor Given a Threshold
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold)
Canonical: https://scaleengineer.com/dsa/problems/find-the-smallest-divisor-given-a-threshold
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Expedia](https://scaleengineer.com/companies/expedia), [PayPal](https://scaleengineer.com/companies/paypal), [ZScaler](https://scaleengineer.com/companies/zscaler), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Millennium](https://scaleengineer.com/companies/millennium)
---
## 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.

**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

**Constraints:**

* `1 <= nums.length <= 5 * 104`
* `1 <= nums[i] <= 106`
* `nums.length <= threshold <= 106`

# Approaches
## Brute Force Linear Scan
This approach involves checking every possible divisor starting from 1. For each divisor, we calculate the sum of the divisions. The first divisor that results in a sum less than or equal to the threshold is the smallest one, so we can return it immediately.
**Time:** O(M * N), where N is the number of elements in `nums` and M is the value of the smallest divisor found. In the worst case, M can be as large as the maximum element in `nums`, making this approach very slow. · **Space:** O(1), as we only use a constant amount of extra space.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient and will likely result in a 'Time Limit Exceeded' error on large test cases.; The number of iterations can be very large, up to the maximum value in `nums`.
### Explanation
We are looking for the smallest positive integer divisor. The search space for the divisor starts at 1. The upper bound can be determined by the largest number in the input array, `nums`, because any divisor larger than `max(nums)` will result in a sum of `nums.length`, which is guaranteed to be less than or equal to `threshold`.

The algorithm iterates through each potential divisor `d` from 1 upwards. For each `d`, it computes the sum of `ceil(num / d)` for all `num` in `nums`.

The ceiling of a division `a / b` can be calculated using integer arithmetic as `(a + b - 1) / b`. This avoids floating-point inaccuracies.

As soon as a divisor is found for which the calculated sum is within the `threshold`, that divisor is returned. Since we are iterating in increasing order, the first one we find will be the smallest.

```java
class Solution {
    // Helper function to calculate the sum for a given divisor
    private int calculateSum(int[] nums, int divisor) {
        int sum = 0;
        for (int num : nums) {
            // Calculate ceiling division: ceil(num / divisor)
            sum += (num + divisor - 1) / divisor;
        }
        return sum;
    }

    public int smallestDivisor(int[] nums, int threshold) {
        // The smallest possible divisor is 1.
        // We can iterate from 1 upwards until we find a valid divisor.
        int divisor = 1;
        while (true) {
            int sum = calculateSum(nums, divisor);
            if (sum <= threshold) {
                return divisor;
            }
            divisor++;
        }
    }
}
```
### Algorithm
- Start with a `divisor` of 1.
- Enter a loop that continues indefinitely.
- Inside the loop, calculate the sum of divisions for the current `divisor`. For each number `num` in `nums`, add `ceil(num / divisor)` to a running total. `ceil(a/b)` can be calculated using integer arithmetic as `(a + b - 1) / b`.
- Check if the calculated `sum` is less than or equal to the `threshold`.
- If it is, we have found the smallest divisor. Return the current `divisor`.
- If not, increment the `divisor` and continue the loop.

## Binary Search on the Answer
A more efficient approach uses binary search on the range of possible answers for the divisor. The key observation is that the sum of divisions is a monotonically decreasing function of the divisor. A larger divisor results in a smaller or equal sum. This property allows us to efficiently search for the smallest divisor that satisfies the condition.
**Time:** O(N * log(M)), where N is the number of elements in `nums` and M is the maximum value in `nums`. The binary search takes O(log M) iterations, and each iteration requires O(N) time to calculate the sum. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Highly efficient, significantly reducing the search space compared to a linear scan.; Guaranteed to find the optimal solution in logarithmic time with respect to the range of possible divisors.
**Cons:** Slightly more complex to conceptualize and implement than the brute-force approach.
### Explanation
The problem asks for the smallest `divisor` that meets a certain condition. This structure suggests that we can search for this `divisor` value. Let's analyze the relationship between the `divisor` and the resulting `sum`. If we define a function `f(d)` that calculates the sum for a given divisor `d`, we can see that if `d1 < d2`, then `f(d1) >= f(d2)`. This monotonic property is perfect for binary search.

The search space for the divisor is from 1 to `max(nums)`. The lower bound is 1, as the divisor must be a positive integer. The upper bound can be the maximum element in the array because any divisor larger than that will yield a sum of `nums.length`, which is a valid solution according to the problem constraints (`nums.length <= threshold`).

We can apply binary search on this range `[1, max(nums)]`. For each middle element `mid` (our candidate divisor), we calculate the sum.
- If `sum <= threshold`, it means `mid` is a potential answer. Since we want the *smallest* such divisor, we try to find an even smaller one by searching in the left half: `[low, mid - 1]`. We store `mid` as our current best answer.
- If `sum > threshold`, the divisor `mid` is too small, leading to a large sum. We need a larger divisor, so we search in the right half: `[mid + 1, high]`.

```java
class Solution {
    // Helper function to calculate the sum for a given divisor
    private int calculateSum(int[] nums, int divisor) {
        int sum = 0;
        for (int num : nums) {
            // Calculate ceiling division: ceil(num / divisor)
            sum += (num + divisor - 1) / divisor;
        }
        return sum;
    }

    public int smallestDivisor(int[] nums, int threshold) {
        int low = 1;
        // The maximum possible divisor is the largest number in the array.
        int high = 0;
        for (int num : nums) {
            high = Math.max(high, num);
        }

        int smallestDivisor = high;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // Avoid division by zero, though low starts at 1.
            if (mid == 0) {
                low = 1;
                continue;
            }

            int sum = calculateSum(nums, mid);

            if (sum <= threshold) {
                // This divisor works. Let's try to find a smaller one.
                smallestDivisor = mid;
                high = mid - 1;
            } else {
                // This divisor is too small, the sum is too large.
                // We need a larger divisor.
                low = mid + 1;
            }
        }
        return smallestDivisor;
    }
}
```
### Algorithm
- Determine the search range for the divisor. The lower bound `low` is 1. The upper bound `high` can be the maximum value in the `nums` array.
- Initialize a variable `result` to store the smallest valid divisor found so far, initially set to `high`.
- Perform a binary search while `low <= high`:
  - a. Calculate the middle point `mid = low + (high - low) / 2`.
  - b. Calculate the sum of divisions using `mid` as the divisor. For each `num` in `nums`, add `(num + mid - 1) / mid` to the sum.
  - c. If the `sum` is less than or equal to `threshold`:
     i. `mid` is a valid divisor. It could be the smallest, so update `result = mid`.
     ii. Try to find an even smaller divisor by narrowing the search to the left half: `high = mid - 1`.
  - d. If the `sum` is greater than `threshold`:
     i. `mid` is too small. We need a larger divisor.
     ii. Narrow the search to the right half: `low = mid + 1`.
- After the loop terminates, `result` will hold the smallest divisor that satisfies the condition.

# Solutions
### CSharp

```csharp
public class Solution {
    public int SmallestDivisor(int[] nums, int threshold) {
        int l = 1;
        int r = nums.Max();
        while (l < r) {
            int mid = (l + r) >> 1;
            int s = 0;
            foreach(int x in nums) {
                s += (x + mid - 1) / mid;
            }
            if (s <= threshold) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
```

### Java

```java
class Solution {
public
  int smallestDivisor(int[] nums, int threshold) {
    int l = 1, r = 1000000;
    while (l < r) {
      int mid = (l + r) >> 1;
      int s = 0;
      for (int x : nums) {
        s += (x + mid - 1) / mid;
      }
      if (s <= threshold) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} threshold * @return {number} */ var smallestDivisor = function ( nums , threshold ) { let l = 1 ; let r = Math . max (... nums ); while ( l < r ) { const mid = ( l + r ) >> 1 ; let s = 0 ; for ( const x of nums ) { s += Math . ceil ( x / mid ); } if ( s <= threshold ) { r = mid ; } else { l = mid + 1 ; } } return l ; };
```

### Python

```python
class Solution:
    def smallestDivisor(self, nums: List[int], threshold: int) -> int: l, r = 1, max(nums) while l < r: mid = (l + r) >> 1 if sum((x + mid - 1) // mid for x in nums) <= threshold: r = mid else: l = mid + 1 return l

```

### CPP

```cpp
class Solution {
public:
  int smallestDivisor(vector<int> &nums, int threshold) {
    int l = 1;
    int r = *max_element(nums.begin(), nums.end());
    while (l < r) {
      int mid = (l + r) >> 1;
      int s = 0;
      for (int x : nums) {
        s += (x + mid - 1) / mid;
      }
      if (s <= threshold) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```