096 — Minimum Eating Speed (Koko Eating Bananas)

095-এ প্রথমবার array ছাড়া binary search করলে। এবার সেই BSoA-র সবচেয়ে চেনা মুখ: minimize ঘরানা। Koko-র সামনে কলার স্তূপ, সময় সীমিত — সবচেয়ে ধীরে (ছোট speed-এ) খেলেও যেন সময়ে শেষ হয়। "সবচেয়ে ছোট speed" শুনলেই মাথায় বাজা উচিত: answer space + feasibility check + monotonicity। এই তিনটে এখানে পাকা করো — 097, 099, 100 সব এই একই ছকে চলে।

Source

• Original source: LeetCode Koko Eating Bananas
• Platform: LeetCode — https://leetcode.com/problems/koko-eating-bananas/
• Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
• Difficulty: Medium
• Pattern: BSoA minimize (সবচেয়ে ছোট feasible উত্তর)
• Basic idea inherited from: 095 — Square Root using Binary Search

1. Problem in simple words

কতগুলো কলার স্তূপ আছে — piles[i] মানে i-তম স্তূপে কয়টা কলা। Koko-র হাতে h ঘণ্টা সময়। সে একটা গতি k (ঘণ্টায় কয়টা কলা) বেছে নেয়, তারপর প্রতি ঘণ্টায় একটা স্তূপ থেকে বড়জোর k টা কলা খায়।

একটা স্তূপে কলা k-এর চেয়ে কম থাকলেও সেই ঘণ্টায় সে অন্য স্তূপ ছোঁয় না (বাকি সময় নষ্ট)। তাই এক স্তূপে লাগে ceil(piles[i] / k) ঘণ্টা। প্রশ্ন: সবচেয়ে ছোট k কত, যাতে সব কলা h ঘণ্টার মধ্যে শেষ হয়?

2. What is the math idea?

মূল idea — minimize ঘরানার BSoA। উত্তর (speed k) সরাসরি বের করা কঠিন, কিন্তু একটা check সহজ: "k speed-এ মোট কত ঘণ্টা লাগে, সেটা কি h-এর মধ্যে?"

আর মূল observation — k বাড়লে মোট সময় কমে (বা সমান)। তাই check-এর উত্তর সাজালে সিঁড়ি F F F T T T: ছোট k-তে সময় বেশি (পারে না, F), একটা জায়গার পর সময় কুলিয়ে যায় (T)। প্রথম T-টাই সবচেয়ে ছোট feasible speed — আমাদের উত্তর।

3. Which basic idea does this inherit from?

095 (Square Root) থেকে — সেখানে শিখেছিলাম "array নেই, কিন্তু monotonic check আছে"। এখানে সেই check পাল্টে গেছে: mid² <= x-এর জায়গায় total_hours(k) <= h।

আরেকটা নতুন স্তর: 095-এ উত্তর ছিল একটা বিশুদ্ধ গাণিতিক জিনিস (√x)। এখানে উত্তর হলো একটা সিদ্ধান্ত (কোন speed বাছব) — আর check-এ আছে একটা ছোট loop (প্রতি স্তূপের সময় যোগ)। এই "check নিজেই একটা ছোট হিসাব" — এটাই minimize পরিবারের চরিত্র, যা 097-100-এ গভীর হবে।

4. Real-life analogy

ভাবো তোমার সামনে কয়েক বালতি পানি, আর একটা মগ। তোমাকে সব বালতি খালি করতে হবে নির্দিষ্ট কত "চাল"-এর (turn) মধ্যে। প্রতি চালে তুমি একটা বালতি থেকে বড়জোর এক মগ পানি তোলো।

মগ ছোট হলে এক বালতি খালি করতেই অনেক চাল লাগে — হয়তো সময়ে কুলোয় না। মগ বড় করলে কম চালে হয়ে যায়। তুমি খুঁজছ সবচেয়ে ছোট মগ যা দিয়ে এখনো সময়ের মধ্যে সব খালি হয়। মগের size = speed k, চাল = ঘণ্টা।

5. Visual explanation

piles = [3, 6, 7, 11], h = 8। প্রতিটা speed k-এর জন্য মোট ঘণ্টা আর "≤ 8?":

k       :  1    2    3    4    5    6 ...
hours   : 27   14   10    8    7    6 ...    hours(k) = Σ ceil(pile/k)
≤ 8?    :  F    F    F    T    T    T ...
                          ↑
                   প্রথম T → উত্তর k = 4

(k=4: ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 ≤ 8 ✓)
(k=3: 1+2+3+4 = 10 > 8 ✗)

সিঁড়ি F F F T T T — k বাড়ালে hours শুধু কমে, তাই একবার T হলে চিরকাল T। প্রথম T = সবচেয়ে ছোট feasible speed।

6. Example input and output

piles            h    ->  min speed   (ব্যাখ্যা)
-----------------------------------------------
[3, 6, 7, 11]    8    ->  4     (উপরের সিঁড়ি)
[30, 11, 23, 4, 20]  5  ->  30   (h = স্তূপ সংখ্যা → প্রতি স্তূপ 1 ঘণ্টায় → max(piles))
[30, 11, 23, 4, 20]  6  ->  23
[312884470]      312884469  ->  2   (এক বিশাল স্তূপ, অঢেল সময়)
[1000000000]     2    ->  500000000  (বড় সংখ্যা)

edge: h যদি স্তূপের সংখ্যার সমান হয়, তবে প্রতি স্তূপ ঠিক 1 ঘণ্টায় শেষ করতে হবে → speed = max(piles)। এটাই answer space-এর সর্বোচ্চ সীমা।

7. Brute force thinking

সবচেয়ে সরল — k = 1 থেকে শুরু করে এক এক করে বাড়াও, প্রথম যে k-তে সময় কুলোয় সেটাই উত্তর:

def min_speed_brute(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)   # ceil division
    k = 1
    while hours(k) > h:
        k += 1
    return k

(p + k - 1) // k হলো ceil(p / k) — integer-এ ceiling। k = 1 থেকে গুনে গুনে এগোই, প্রথম যে speed-এ hours(k) <= h সেখানেই থামি। ঠিক উত্তরই দেয়।

8. Why brute force may be slow

speed সর্বোচ্চ max(piles) পর্যন্ত যেতে পারে, আর প্রতিটা k-তে hours(k) গুনতে O(n)। তাই worst case O(n · max(piles))। max(piles) 10^9 হলে এটা একদম অচল।

piles-এ max = 10^9, n = 10^4 হলে:
  brute force   : ~10^13 operation  (অসম্ভব ধীর, TLE)
  binary search : ~30 × 10^4 ≈ 3×10^5  (O(n log max), দ্রুত)

মূল শিক্ষা: hours(k) monotonic — তাই k এক এক করে না বাড়িয়ে binary search-এ অর্ধেক বাদ দাও।

9. Better thinking

মূল insight: hours(k) monotonic decreasing, তাই hours(k) <= h-এর সিঁড়ি F F F T T T। প্রথম T খুঁজি (lower bound-এর সেই চেনা কাঠামো, কিন্তু check-টা computed):

def min_eating_speed(piles, h):
    def can(k):                                  # k speed-এ h ঘণ্টায় পারা যায়?
        return sum((p + k - 1) // k for p in piles) <= h

    lo, hi = 1, max(piles)                       # hi নিশ্চিত feasible
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid                             # পারা যায় → আরও ছোট চেষ্টা
        else:
            lo = mid + 1                         # পারা যায় না → বড় লাগবে
    return lo

প্রতি ধাপে অর্ধেক, প্রতি check O(n) → O(n log(max(piles)))।

10. Thinking tweak

আসল মোচড়: "সবচেয়ে ছোট valid speed" সরাসরি বের না করে, প্রতিটা guess-কে একটা হ্যাঁ/না check-এ পরিণত করো — can(k) = 'এই speed-এ পারা যায়?' — তারপর প্রথম T খোঁজো।

আর minimize-এর move মনে রাখো: check পাশ করলে hi = mid (আরও ছোট পেতে পারি কিনা দেখি), fail করলে lo = mid + 1 (ছোট দিয়ে হয়নি, বড় লাগবে)। 098-এর maximize-এ এই move ঠিক উল্টে যাবে — তাই সিঁড়ির ছবি (F বাঁয়ে না ডানে?) আগে এঁকে নাও, তারপর move ঠিক করো। মুখস্থ না, সিঁড়ি দেখে।

11. Step-by-step dry run

piles = [3, 6, 7, 11], h = 8 চালাই (lo=1, hi=max=11):

step	lo	hi	mid	hours(mid)	≤ 8?	সিদ্ধান্ত
1	1	11	6	1+1+2+2 = 6	হ্যাঁ	hi = mid = 6
2	1	6	3	1+2+3+4 = 10	না	lo = mid + 1 = 4
3	4	6	5	1+2+2+3 = 8	হ্যাঁ	hi = mid = 5
4	4	5	4	1+2+2+3 = 8	হ্যাঁ	hi = mid = 4
—	4	4	—	—	—	lo == hi = 4 → return 4

উত্তর 4 ✓। লক্ষ করো step 3 আর 4-এ দুবার hours = 8 ≤ 8 (T), কিন্তু আমরা থামি না — আরও ছোট খুঁজি, যতক্ষণ lo আর hi মিলে যায়। সেটাই সবচেয়ে ছোট feasible।

12. Python solution

def min_eating_speed(piles, h):
    """সবচেয়ে ছোট speed k যাতে সব কলা h ঘণ্টায় শেষ হয়।"""
    def can(k):                                  # feasibility check
        return sum((p + k - 1) // k for p in piles) <= h

    lo, hi = 1, max(piles)                       # lo=1 (0 দিলে div by zero), hi=max feasible
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid                             # পারা যায় → আরও ছোট চেষ্টা
        else:
            lo = mid + 1                         # পারা যায় না → বড় লাগবে
    return lo


import math


def min_speed_brute(piles, h):                   # ছোট input-এ cross-check
    def hours(k):
        return sum((p + k - 1) // k for p in piles)
    k = 1
    while hours(k) > h:
        k += 1
    return k


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert min_eating_speed([3, 6, 7, 11], 8) == 4
assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30   # h = n → max(piles)
assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23
assert min_eating_speed([312884470], 312884469) == 2
assert min_eating_speed([1000000000], 2) == 500000000   # বড় সংখ্যা

# brute force-এর সাথে cross-check (ছোট মানে)
import random
random.seed(7)
for _ in range(300):
    n = random.randint(1, 6)
    piles = [random.randint(1, 20) for _ in range(n)]
    h = random.randint(n, 3 * sum(piles))           # h ≥ n যাতে সবসময় feasible
    assert min_eating_speed(piles, h) == min_speed_brute(piles, h)

# উত্তরের ঠিক আগের speed-এ সময় কুলোয় না (boundary যাচাই)
piles, h = [3, 6, 7, 11], 8
k = min_eating_speed(piles, h)
assert sum((p + k - 1) // k for p in piles) <= h          # k পারে
assert sum((p + (k - 1) - 1) // (k - 1) for p in piles) > h  # k-1 পারে না

print(min_eating_speed([3, 6, 7, 11], 8))         # 4
print(min_eating_speed([30, 11, 23, 4, 20], 5))   # 30
print("সব test pass!")

13. Line-by-line explanation

def can(k): return sum((p + k - 1) // k for p in piles) <= h

feasibility check। (p + k - 1) // k হলো ceiling division — এক স্তূপে লাগা ঘণ্টা। সব স্তূপের যোগ ≤ h হলে k-তে পারা যায়। ceiling জরুরি: p // k লিখলে ভগ্নাংশ ঘণ্টা গুনত না, ভুল speed-কে feasible বলত।

lo, hi = 1, max(piles)

answer space। lo = 1 কারণ speed 0 মানে কখনো খাওয়া শেষ হয় না (আর // 0 crash)। hi = max(piles) কারণ এর সমান বা বেশি speed-এ প্রতি স্তূপ ঠিক ≤ 1 ঘণ্টায় শেষ — সবসময় feasible, তাই নিরাপদ উপরের সীমা।

if can(mid): hi = mid

mid speed-এ পারা যায় → এটা একটা valid উত্তর, কিন্তু আরও ছোট হতে পারে। তাই mid রেখে ডান অর্ধেক বাদ (hi = mid)।

else: lo = mid + 1

mid-এ পারা যায় না → mid আর তার বাঁয়ের সব speed-ও পারবে না (monotonic)। তাই mid সহ বাঁ অর্ধেক বাদ।

cross-check-এ random ছোট input-এ brute force-এর সাথে, আর boundary যাচাইয়ে দেখছি উত্তর k পারে কিন্তু k-1 পারে না। সব মিললে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

4
30
সব test pass!

প্রথম: min_eating_speed([3,6,7,11], 8) = 4 (dry run-এর ফল)। দ্বিতীয়: [30,11,23,4,20] h=5-এ = 30 (h = স্তূপ সংখ্যা, তাই প্রতি স্তূপ 1 ঘণ্টায় → max)। আগের সব assert — random cross-check (300 কেস) আর boundary যাচাই — চুপচাপ pass। সবশেষে সব test pass!।

15. Time complexity

O(n log(max(piles))) — answer space [1, max(piles)]-এ binary search (log(max) ধাপ), প্রতি ধাপে check-এ সব n স্তূপ ঘোরা (O(n))। n = 10^4, max = 10^9 হলে ≈ 3×10^5 — চোখের নিমেষ।

16. Space complexity

O(1) — check-এর sum(...) generator extra list বানায় না; শুধু lo, hi, mid আর running sum। input ছাড়া বাড়তি জায়গা প্রায় শূন্য।

17. Common mistakes

1. ceiling-এর বদলে floor — p // k লিখলে ভগ্নাংশ ঘণ্টা গোনা হয় না → ভুল speed feasible মনে হয়। (p + k - 1) // k বা -(-p // k) ব্যবহার করো।
2. lo = 0 দিয়ে শুরু — speed 0-এ // 0 crash, আর 0 কখনো feasible না; lo = 1।
3. hi খুব ছোট রাখা — hi < max(piles) দিলে উত্তরটাই range-এর বাইরে পড়তে পারে; hi = max(piles) সবসময় feasible।
4. minimize-এর move উল্টে ফেলা — check পাশ করলে hi = mid (ছোট খোঁজো), fail-এ lo = mid+1। 098-এর maximize-এর সাথে গুলিও না।
5. while lo <= hi লেখা — hi = mid থাকায় infinite loop; এই template-এ while lo < hi।

18. Harder problems that inherit this idea

• LeetCode — Capacity to Ship Packages Within D Days (https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/) — হুবহু একই কাঠামো; পরের problem 097-এই এর বিস্তারিত।
• LeetCode — Minimum Number of Days to Make m Bouquets (https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/) — দিন-এর উপর একই minimize BSoA, check-এ greedy গোনা।
• 097 (Ship Packages), 099 (Allocate Pages), 100 (Split Array) — এই repo-রই পরের ধাপ; সব এই minimize template-এর ভিন্ন গল্প।

19. Pattern learned

BSoA minimize (smallest feasible answer) — answer space [lo, hi] + can(guess) check (এক পাসে হিসাবযোগ্য) + monotonicity; check পাশ → hi = mid, fail → lo = mid + 1। বড় শিক্ষা: "সবচেয়ে ছোট X যাতে শর্ত মেটে" শুনলেই — guess করো, feasibility check লেখো, প্রথম T খোঁজো। ceiling division আর feasible hi — দুটো খুঁটিনাটি ভুললেই bug।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Koko = minimize BSoA; answer = speed, check = Σ ceil(pile/k) ≤ h, সিঁড়ি FFFTTT, প্রথম T-ই উত্তর। lo=1, hi=max(piles); পাশ→hi=mid, fail→lo=mid+1। 'সবচেয়ে ছোট speed/capacity যাতে...' = এই template।"

পরের ধাপ → 097 — Ship Packages Within D Days (হুবহু এই ছক: speed→capacity, ঘণ্টা→দিন)। সম্পর্কিত → 095 — Square Root using Binary Search।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

minimize BSoA — check can(k) পাশ করলে hi = mid (আরও ছোট), fail করলে lo = mid + 1। ceiling-এ Math.ceil।

// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function minEatingSpeed(piles, h) {
  const can = (k) => piles.reduce((acc, p) => acc + Math.ceil(p / k), 0) <= h;
  let lo = 1, hi = Math.max(...piles);       // lo=1 (k=0 হলে div by zero), hi=max feasible
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (can(mid)) hi = mid;                   // পারা যায় → আরও ছোট চেষ্টা
    else lo = mid + 1;                         // পারা যায় না → বড় লাগবে
  }
  return lo;
}

// brute — cross-check
function minSpeedBrute(piles, h) {
  const hours = (k) => piles.reduce((a, p) => a + Math.ceil(p / k), 0);
  let k = 1;
  while (hours(k) > h) k++;
  return k;
}

// ---- test cases (file-এর example + edge case) ----
assert(minEatingSpeed([3, 6, 7, 11], 8) === 4, "basic");
assert(minEatingSpeed([30, 11, 23, 4, 20], 5) === 30, "h=n → max(piles)");
assert(minEatingSpeed([30, 11, 23, 4, 20], 6) === 23, "h=6");
assert(minEatingSpeed([312884470], 312884469) === 2, "এক বিশাল স্তূপ");
assert(minEatingSpeed([1000000000], 2) === 500000000, "বড় সংখ্যা");
// brute-এর সাথে random ছোট input জুড়ে মিল
for (let t = 0; t < 300; t++) {
  const n = 1 + Math.floor(Math.random() * 6);
  const piles = [];
  for (let i = 0; i < n; i++) piles.push(1 + Math.floor(Math.random() * 20));
  const sum = piles.reduce((a, b) => a + b, 0);
  const h = n + Math.floor(Math.random() * (3 * sum - n + 1));  // h ≥ n
  assert(minEatingSpeed(piles, h) === minSpeedBrute(piles, h), "cross-check");
}
console.log("সব JS test pass!");

JS টীকা: ceiling-এ Math.ceil(p / k) সহজ, কিন্তু খুব বড় p-তে float নির্ভুলতা ঝুঁকি — safe integer রূপ Math.floor((p + k - 1) / k)। Math.max(...piles) বিশাল array-তে spread call-stack ছাড়াতে পারে; তখন loop/reduce দিয়ে max বের করো।

22. TypeScript solution (with test cases)

function minEatingSpeed(piles: number[], h: number): number {
  const can = (k: number): boolean =>
    piles.reduce((acc, p) => acc + Math.ceil(p / k), 0) <= h;
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (can(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function expect(actual: number, expected: number, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number[], number, number]> = [
  [[3, 6, 7, 11], 8, 4], [[30, 11, 23, 4, 20], 5, 30],
  [[30, 11, 23, 4, 20], 6, 23], [[1000000000], 2, 500000000],
];
for (const [p, h, want] of cases) expect(minEatingSpeed(p, h), want, `h=${h}`);
console.log("সব TS test pass!");

TS টীকা: can ভেতরে return boolean annotate করায় feasibility check ভুলে number return করলে (যেমন <= h লিখতে ভুলে যাওয়া) compile-time-এ ধরা পড়ে — minimize move-এর শর্ত নিরাপদ থাকে।

23. কোথায় কাজে লাগে (real-world use)

• Rate / capacity provisioning: নির্দিষ্ট deadline-এ কাজ শেষ করতে সবচেয়ে ছোট throughput/server/bandwidth — autoscaling, SLA planning।
• Shipping / load balancing: D দিনে সব package পাঠাতে সবচেয়ে ছোট জাহাজ-capacity (Ship Packages — হুবহু এই ছক)।
• Resource allocation: সবচেয়ে ছোট buffer/batch size যাতে সময়/মেমরির মধ্যে কাজ হয়।
• Threshold tuning: monotonic metric-এ সবচেয়ে ছোট threshold যা শর্ত মেটায় (latency, error budget)। মূল pattern — "'সবচেয়ে ছোট X যাতে শর্ত মেটে' = guess + feasibility check + প্রথম T" — minimize binary-search-on-answer জুড়ে বড় ছবিতে ফেরে।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।