Smallest Divisor With a Given Sum Threshold

You are given an array of positive integers nums and an integer threshold. Choose a positive integer divisor, divide every element of nums by it, round each result up to the nearest integer, and sum the rounded values. Find the smallest divisor such that this sum is less than or equal to threshold.

Input: The first line contains two integers n and threshold. The second line contains n space-separated positive integers, the array nums. Output: Print a single integer: the smallest valid divisor.

1 <= n <= 5*10^4 1 <= nums[i] <= 10^6 n <= threshold <= 10^6

This is another clean instance of 'binary search on the answer' with a monotonic sum-based feasibility check - the exact same underlying pattern as the eating-speed and ship-capacity problems, just with a ceiling-division-based feasibility formula instead of a greedy day/hour count.

Find the smallest positive integer divisor such that dividing every array element by it (rounding up) and summing the results stays within a given threshold. Brute force: Try every possible divisor starting from 1 upward, checking feasibility for each, until finding the first one that works - this costs O(max value * n) in the worst case, too slow when values can be up to 10^6. Optimised: Since the summed ceiling-division total is a MONOTONIC (non-increasing) function of the divisor, binary searching directly on the divisor - checking feasibility with an O(n) sum computation at each candidate - finds the minimum feasible divisor in O(n log(max value)).

1. Recognize that the divisor can be as small as 1, and never needs to exceed the LARGEST value in the array (dividing by anything at least that large already makes every term at most 1). 2. For a candidate divisor d, compute the sum of ceil(nums[i] / d) across the whole array in O(n). 3. Since that sum only DECREASES (or stays the same) as d increases, binary search for the smallest d whose sum is <= threshold.

Time: O(n log(max value)) - each binary search step's feasibility check costs O(n). Space: O(1) extra space beyond the input array.

threshold exactly equal to n forces the largest possible divisor (every term must round down to exactly 1); n = 1.

Be ready to point out the tight, meaningful search bounds (1 to the largest array value) rather than an arbitrary large number - stating precise bounds shows a deeper understanding of why the search range is correct and efficient.