2.2 Binary Search on Answer

Demo: Koko Eating Bananas — LC 875 (Medium — Amazon/Google High)

Statement (Demo): n পাইল কলা দেওয়া, প্রতি পাইলে piles[i]টা কলা। h ঘণ্টায় সব কলা শেষ করতে হবে। প্রতি ঘণ্টায় একটাই পাইল থেকে সর্বোচ্চ kটা কলা খেতে পারে (পাইল ছোট হলে পুরো পাইলটা শেষ)। সর্বনিম্ন কত k হলে h ঘণ্টার মধ্যে সব শেষ হবে বলুন। উদাহরণ: piles=[3,6,7,11], h=8 → 4 | ⚡ n ≤ 10⁴, 1 ≤ piles[i] ≤ 10⁹, n ≤ h ≤ 10⁹

Approach: array-তে না, উত্তরের space-এ search করুন: speed 1 থেকে max(piles)। canFinish(k) monotonic — তাই সবচেয়ে ছোট feasible k বের করতে binary search।

function minEatingSpeed(piles, h) {
  const canFinish = (k) => piles.reduce((t, p) => t + Math.ceil(p / k), 0) <= h;
  let lo = 1,
    hi = Math.max(...piles);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (canFinish(mid))
      hi = mid; // আরও ছোট speed চেষ্টা
    else lo = mid + 1;
  }
  return lo;
}

Complexity: Time O(n log max), Space O(1)