Find the Smallest Divisor Given a Threshold

Problem (yeniden ifade)

Pozitif tamsayı dizisi nums ve bir threshold verilir. Her nums[i]’yi pozitif d ile ceil bölüp topla; bu toplam threshold’u aşmayacak en küçük d’yi döndür.

Sezgi

Daha büyük divisor → daha küçük toplam; divisor üzerinde binary search.

Yaklaşımlar

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

Şablon bağlantısı

Bölen üzerine binary search; tavan toplamı fizibilite kontrolü.

Yansıma

• Küçük divisor daha büyük toplam üretir (ceil). Monotonik ters: divisor artınca toplam düşer.
• lo = 1, hi = max(nums). threshold < n ise imkânsız mı? (ceil en az 1.)
• divisor = 1 tüm nums toplamı; taşma?