Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

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

Tested only

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;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?