Problem link ও উৎস
- **Original source:** LeetCode Koko Eating Bananas
- **Platform:** LeetCode —
- **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
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো কলার স্তূপ আছে — `piles[i]` মানে i-তম স্তূপে কয়টা কলা। Koko-র হাতে `h` ঘণ্টা সময়। সে একটা গতি `k` (ঘণ্টায় কয়টা কলা) বেছে নেয়, তারপর প্রতি ঘণ্টায় একটা স্তূপ থেকে বড়জোর `k` টা কলা খায়।
একটা স্তূপে কলা k-এর চেয়ে কম থাকলেও সেই ঘণ্টায় সে অন্য স্তূপ ছোঁয় না (বাকি সময় নষ্ট)। তাই এক স্তূপে লাগে `ceil(piles[i] / k)` ঘণ্টা। প্রশ্ন: **সবচেয়ে ছোট k** কত, যাতে সব কলা `h` ঘণ্টার মধ্যে শেষ হয়?
### Input ও output {#6-example-input-and-output}
```text
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-এর সর্বোচ্চ সীমা।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার সামনে কয়েক বালতি পানি, আর একটা মগ। তোমাকে সব বালতি খালি করতে হবে নির্দিষ্ট কত "চাল"-এর (turn) মধ্যে। প্রতি চালে তুমি **একটা** বালতি থেকে বড়জোর এক মগ পানি তোলো।
মগ ছোট হলে এক বালতি খালি করতেই অনেক চাল লাগে — হয়তো সময়ে কুলোয় না। মগ বড় করলে কম চালে হয়ে যায়। তুমি খুঁজছ সবচেয়ে **ছোট মগ** যা দিয়ে এখনো সময়ের মধ্যে সব খালি হয়। মগের size = speed k, চাল = ঘণ্টা।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ গভীর হবে।
### ভেতরের অঙ্ক {#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 — আমাদের উত্তর।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল — k = 1 থেকে শুরু করে এক এক করে বাড়াও, প্রথম যে k-তে সময় কুলোয় সেটাই উত্তর:
```python
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 হলে এটা একদম অচল।
```text
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):
```python
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 ঠিক করো। মুখস্থ না, সিঁড়ি দেখে।
### ছবিতে বোঝা {#5-visual-explanation}
`piles = [3, 6, 7, 11], h = 8`। প্রতিটা speed k-এর জন্য মোট ঘণ্টা আর "≤ 8?":
```text
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।
### ছোট input-এ ধাপে ধাপে {#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।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
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 বলত।
```text
lo, hi = 1, max(piles)
```
answer space। `lo = 1` কারণ speed 0 মানে কখনো খাওয়া শেষ হয় না (আর `// 0` crash)। `hi = max(piles)` কারণ এর সমান বা বেশি speed-এ প্রতি স্তূপ ঠিক ≤ 1 ঘণ্টায় শেষ — সবসময় feasible, তাই নিরাপদ উপরের সীমা।
```text
if can(mid): hi = mid
```
mid speed-এ পারা যায় → এটা একটা valid উত্তর, কিন্তু আরও ছোট হতে পারে। তাই mid রেখে ডান অর্ধেক বাদ (`hi = mid`)।
```text
else: lo = mid + 1
```
mid-এ পারা যায় না → mid আর তার বাঁয়ের সব speed-ও পারবে না (monotonic)। তাই mid সহ বাঁ অর্ধেক বাদ।
cross-check-এ random ছোট input-এ brute force-এর সাথে, আর boundary যাচাইয়ে দেখছি উত্তর k পারে কিন্তু k-1 পারে না। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
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!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
minimize BSoA — check `can(k)` পাশ করলে `hi = mid` (আরও ছোট), fail করলে `lo = mid + 1`। ceiling-এ `Math.ceil`।
```javascript
// 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 বের করো।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
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