Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbinary-search-on-answer

Find the Smallest Divisor Given a Threshold

Problem (restated)

Find the smallest positive divisor such that the sum of ceil divisions of nums is ≤ threshold.

Intuition

Larger divisor → smaller sum; binary search the divisor.

Approaches

Binary search divisor

Unverified

Time O(n log M)Space O(1)

Idea. lo=1, hi=max(nums). mid ok if sum(ceil(x/mid)) ≤ threshold.

Walkthrough. [1,2,5,9], threshold=6 → divisor 5.

Trade-offs. Same pattern as Koko / ship capacity.

Solution

export function smallestDivisor(nums: number[], threshold: number): number {
  let lo = 1, hi = Math.max(...nums);
  const ok = (d: number) => {
    let s = 0;
    for (const x of nums) s += Math.ceil(x / d);
    return s <= threshold;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

export function smallestDivisor(nums: number[], threshold: number): number {
  let lo = 1, hi = Math.max(...nums);
  const ok = (d: number) => {
    let s = 0;
    for (const x of nums) s += Math.ceil(x / d);
    return s <= threshold;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Template connection

Binary search on the divisor; sum of ceils is the feasibility check.

Reflection

A smaller divisor produces a larger sum of ceils. As the divisor grows, the sum falls.
lo = 1 and hi = max(nums). If the threshold is below n, is it impossible? Each ceil is at least 1.
divisor = 1 sums every value in nums. Can that sum overflow?