coding•DSA & Problem Solving•Binary Search & Optimization
Find Smallest Divisor Given a Threshold
Problem Statement
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 division is rounded to the nearest integer greater than or equal to that element (i.e. `ceil(num / divisor)`).
It is guaranteed that there will be an answer.
### Constraints
- `1 <= nums.length <= 5 * 10^4`
- `1 <= nums[i] <= 10^6`
- `nums.length <= threshold <= 10^6`
### Input Format
First line contains the integer `threshold`.
Second line contains space-separated integers representing `nums`.
### Output Format
Print the smallest integer divisor.
Sample Cases
Example 1Sample Case
Input: 6
1 2 5 9
Output: 5
Example 2Sample Case
Input: 44
44 22 33 11 1
Output: 3
Example 3Sample Case
Input: 6
1
Output: 1
Example 4Sample Case
Input: 6
6
Output: 1
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.