Problem link ও উৎস
- **Original source:** LeetCode Capacity to Ship Packages Within D Days
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Medium
- **Pattern:** BSoA minimize (সবচেয়ে ছোট feasible capacity)
- **Basic idea inherited from:** 096 — Minimum Eating Speed
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা conveyor belt-এ কতগুলো package সারিবদ্ধ, `weights[i]` হলো i-তম package-এর ওজন। তোমাকে এগুলো `days` দিনের মধ্যে জাহাজে পাঠাতে হবে।
নিয়ম: প্রতিদিন তুমি belt-এর **সামনে থেকে ক্রম অনুযায়ী** যত package নিতে চাও নাও, কিন্তু একদিনের মোট ওজন জাহাজের **capacity** ছাড়াতে পারবে না। ক্রম বদলানো যাবে না, একটা package ভাঙা যাবে না। প্রশ্ন: জাহাজের **সবচেয়ে ছোট capacity** কত, যাতে ঠিক `days` দিনে (বা কম) সব পাঠানো যায়?
### Input ও output {#6-example-input-and-output}
```text
weights days -> min capacity (ব্যাখ্যা)
----------------------------------------------------------------
[1,2,3,4,5,6,7,8,9,10] 5 -> 15
[3,2,2,4,1,4] 3 -> 6
[1,2,3,1,1] 4 -> 3
[10,20,30] 1 -> 60 (1 দিন → সব একসাথে → sum)
[10,20,30] 3 -> 30 (3 দিন → প্রতি package আলাদা → max)
```
দুটো সীমান্ত edge: **days = 1** হলে এক দিনেই সব → capacity = `sum(weights)`। **days = package সংখ্যা** হলে প্রতি package আলাদা দিনে → capacity = `max(weights)`। এই দুটোই answer space-এর দুই প্রান্ত।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি প্রতিদিন একটা ব্যাগে করে বাজার থেকে জিনিস আনো, কিন্তু জিনিসগুলো একটা লাইনে সাজানো আর তুমি লাইন ভেঙে নিতে পারো না — সামনে থেকে যা পড়ে তাই।
ব্যাগ ছোট হলে অল্প জিনিসে ভরে যায়, অনেক দিন লাগে সব আনতে। ব্যাগ বড় হলে কম দিনে হয়ে যায়। তুমি খুঁজছ সবচেয়ে **ছোট ব্যাগ** যা দিয়ে এখনো নির্দিষ্ট কয় দিনে সব আনা যায়। ব্যাগের size = capacity, যত দিন = days।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
096 (Minimum Eating Speed) থেকে — কাঠামো এক, শুধু গল্প আর check বদলেছে:
- Koko: answer = speed, check = `Σ ceil(pile/k) <= h`
- এখানে: answer = capacity, check = `প্রয়োজনীয় দিন <= days`
কিন্তু একটা গুরুত্বপূর্ণ পার্থক্য check-এর **ভেতরে**: Koko-তে প্রতি স্তূপ আলাদা, তাই সরাসরি যোগ। এখানে packages **ক্রমে সাজানো ও অবিভাজ্য** — তাই দিন গুনতে greedy লাগে (যোগ করতে করতে capacity ছাড়ালেই নতুন দিন)। এই "check নিজেই একটা greedy পাস" — এটাই 099, 100-এর সাথে এর গভীর মিল।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
আবার **minimize ঘরানার BSoA** — হুবহু 096-এর কাঠামো। উত্তর (capacity) সরাসরি বের না করে check লিখি: "এই capacity-তে কয় দিন লাগে, সেটা কি `days`-এর মধ্যে?"
observation — **capacity বাড়লে দিন কমে (বা সমান)**। তাই check-এর সিঁড়ি **F F F T T T**: ছোট capacity-তে বেশি দিন লাগে (পারে না), একটা জায়গার পর কুলিয়ে যায়। প্রথম T = সবচেয়ে ছোট feasible capacity।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
capacity = `max(weights)` থেকে শুরু (এর কম হলে সবচেয়ে ভারী package-ই ওঠে না) করে এক এক করে বাড়াও, প্রথম যে capacity-তে দিন কুলোয় সেটাই উত্তর:
```python
def ship_brute(weights, days):
def need(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap: # আজ আর ধরছে না → নতুন দিন
d += 1
cur = 0
cur += w
return d
cap = max(weights)
while need(cap) > days:
cap += 1
return cap
```
`need(cap)` greedy-তে দিন গোনে: যোগ করতে থাকো, capacity ছাড়ালে নতুন দিন শুরু। তারপর `max(weights)` থেকে capacity এক এক করে বাড়িয়ে প্রথম feasible-এ থামি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
capacity `max(weights)` থেকে `sum(weights)` পর্যন্ত যেতে পারে — সেই পরিসর বিশাল (10^9 স্কেল)। প্রতিটা capacity-তে `need` গুনতে O(n)। তাই **O(n · sum(weights))** — অচল।
```text
sum(weights) ≈ 5×10^9, n = 5×10^4 হলে:
brute force : ~10^14 operation (অসম্ভব ধীর, TLE)
binary search : ~33 × 5×10^4 ≈ 1.7×10^6 (O(n log sum), দ্রুত)
```
মূল শিক্ষা: `need(cap)` monotonic — তাই capacity এক এক করে না বাড়িয়ে binary search-এ অর্ধেক বাদ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: `need(cap)` monotonic decreasing, তাই `need(cap) <= days`-এর সিঁড়ি **F F F T T T**। প্রথম T খুঁজি:
```python
def ship_within_days(weights, days):
def can(cap): # cap-এ days দিনে পারা যায়?
d, cur = 1, 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d <= days
lo, hi = max(weights), sum(weights) # lo: সবচেয়ে ভারী তো উঠতেই হবে; hi: এক দিনে সব
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # পারা যায় → আরও ছোট চেষ্টা
else:
lo = mid + 1 # পারা যায় না → বড় লাগবে
return lo
```
প্রতি ধাপে অর্ধেক, প্রতি check O(n) → O(n log(sum(weights)))।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল মোচড় দুটো। প্রথমত (096-এর মতোই): **capacity সরাসরি না খুঁজে, প্রতিটা guess-কে check-এ পরিণত করো — `can(cap)` = 'এই capacity-তে days দিনে কুলোয়?'।**
দ্বিতীয়ত, নতুন: **answer space-এর সীমা সাবধানে।** `lo = max(weights)` (এর কম হলে সবচেয়ে ভারী package কোনো দিনেই ওঠে না — কখনো feasible না), `hi = sum(weights)` (এক দিনে সব — সবসময় feasible)। 096-এ `lo=1, hi=max`; এখানে `lo=max, hi=sum` — সীমা problem-এর গল্প থেকে আসে, মুখস্থ না। সিঁড়ির দুই প্রান্তে কোনটা নিশ্চিত F আর কোনটা নিশ্চিত T — সেটা ভেবে নাও।
### ছবিতে বোঝা {#5-visual-explanation}
`weights = [1,2,3,4,5,6,7,8,9,10], days = 5`। কয়েকটা capacity-র জন্য দিন আর "≤ 5?":
```text
capacity : 14 15 16 17 ...
days_need: 6 5 5 5 ... (greedy-তে দিন গুনে)
≤ 5? : F T T T ...
↑
প্রথম T → উত্তর capacity = 15
cap=15-এ দিন ভাগ: [1,2,3,4,5]=15 | [6,7]=13 | [8]=8 (9 নিলে 17>15) | [9]=9 | [10]=10 → 5 দিন ✓
cap=14-এ: [1,2,3,4]=10 (5 নিলে 15>14) | [5,6]=11 | [7]=7 | [8]=8 | [9]=9 | [10] → 6 দিন ✗
```
সিঁড়ি **F F F T T T** — capacity বাড়লে দিন কমে, প্রথম T = সবচেয়ে ছোট feasible।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`weights = [1,2,3,4,5,6,7,8,9,10], days = 5` (`lo=max=10, hi=sum=55`):
| step | lo | hi | mid | need(mid) | ≤ 5? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 10 | 55 | 32 | 2 | হ্যাঁ | hi = mid = 32 |
| 2 | 10 | 32 | 21 | 3 | হ্যাঁ | hi = mid = 21 |
| 3 | 10 | 21 | 15 | 5 | হ্যাঁ | hi = mid = 15 |
| 4 | 10 | 15 | 12 | 6 | না | lo = mid + 1 = 13 |
| 5 | 13 | 15 | 14 | 6 | না | lo = mid + 1 = 15 |
| — | 15 | 15 | — | — | — | lo == hi = 15 → return 15 |
উত্তর 15 ✓। step 3-এ `need = 5 ≤ 5` (T), কিন্তু থামি না — আরও ছোট চেষ্টা; 12 আর 14-এ fail করে শেষে 15-এ স্থির। সেটাই সবচেয়ে ছোট feasible capacity।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def ship_within_days(weights, days):
"""সবচেয়ে ছোট capacity যাতে weights ক্রমে days দিনে পাঠানো যায়।"""
def can(cap): # feasibility: days দিনে কুলোয়?
d, cur = 1, 0 # অন্তত 1 দিন লাগবেই
for w in weights:
if cur + w > cap: # আজ আর ধরছে না → নতুন দিন
d += 1
cur = 0
cur += w
return d <= days
lo, hi = max(weights), sum(weights) # lo নিশ্চিত নিচ, hi নিশ্চিত feasible
while lo < hi:
mid = (lo + hi) // 2
if can(mid):
hi = mid # পারা যায় → আরও ছোট
else:
lo = mid + 1 # পারা যায় না → বড় লাগবে
return lo
def ship_brute(weights, days): # ছোট input-এ cross-check
def need(cap):
d, cur = 1, 0
for w in weights:
if cur + w > cap:
d += 1
cur = 0
cur += w
return d
cap = max(weights)
while need(cap) > days:
cap += 1
return cap
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert ship_within_days([1,2,3,4,5,6,7,8,9,10], 5) == 15
assert ship_within_days([3,2,2,4,1,4], 3) == 6
assert ship_within_days([1,2,3,1,1], 4) == 3
assert ship_within_days([10,20,30], 1) == 60 # 1 দিন → sum
assert ship_within_days([10,20,30], 3) == 30 # n দিন → max
assert ship_within_days([5], 1) == 5 # এক package
# brute force-এর সাথে random cross-check
import random
random.seed(11)
for _ in range(300):
n = random.randint(1, 7)
w = [random.randint(1, 15) for _ in range(n)]
days = random.randint(1, n) # 1 ≤ days ≤ n যাতে feasible
assert ship_within_days(w, days) == ship_brute(w, days)
# boundary: উত্তর cap পারে, cap-1 পারে না
w, days = [1,2,3,4,5,6,7,8,9,10], 5
cap = ship_within_days(w, days)
def need(weights, c):
d, cur = 1, 0
for x in weights:
if cur + x > c:
d += 1; cur = 0
cur += x
return d
assert need(w, cap) <= days
assert need(w, cap - 1) > days
print(ship_within_days([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(ship_within_days([10,20,30], 1)) # 60
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
d, cur = 1, 0
```
`d` = দিন গণনা (অন্তত 1 দিন তো লাগবেই), `cur` = আজকের দিনে এ পর্যন্ত তোলা মোট ওজন।
```text
if cur + w > cap: d += 1; cur = 0
```
আজকের ওজনে এই package যোগ করলে capacity ছাড়িয়ে যায় → এই package আজ নয়, **নতুন দিন** শুরু (`d += 1`), আজকের বোঝা শূন্য থেকে শুরু।
```text
cur += w
```
package-টা চলতি দিনে যোগ করি। (লক্ষ করো: `cur > cap` কখনো হবে না কারণ `lo >= max(weights)`, তাই একটা package একা সবসময় ধরে।)
```text
lo, hi = max(weights), sum(weights)
```
answer space। `lo = max(weights)`: সবচেয়ে ভারী package তো এক দিনে উঠতেই হবে, তার চেয়ে ছোট capacity কখনো কাজ করবে না। `hi = sum(weights)`: এক দিনেই সব — সবসময় feasible, নিরাপদ উপরের সীমা।
```text
if can(mid): hi = mid / else: lo = mid + 1
```
minimize move: পারলে ছোট খুঁজি (`hi = mid`), না পারলে বড় লাগবে (`lo = mid + 1`)। 096-এর সাথে হুবহু এক।
cross-check-এ random brute force আর boundary (cap পারে, cap-1 পারে না)। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
15
60
সব test pass!
```
প্রথম: `ship_within_days([1..10], 5)` = 15 (dry run-এর ফল)। দ্বিতীয়: `[10,20,30]` days=1-এ = 60 (এক দিন → sum)। আগের সব `assert` — random cross-check (300 কেস) আর boundary যাচাই — চুপচাপ pass। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n log(sum(weights)))** — answer space `[max, sum]`-এ binary search (log(sum) ধাপ), প্রতি ধাপে check-এ সব n package-এ greedy পাস (O(n))। বড় input-এও দ্রুত।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — check-এ শুধু `d`, `cur` দুটো counter; কোনো বাড়তি array না। `lo`, `hi`, `mid` ছাড়া আর কিছু লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`lo = 1` বা `lo = 0` দিয়ে শুরু** — capacity যদি `max(weights)`-এর ছোট হয়, সবচেয়ে ভারী package কোনো দিনেই ওঠে না; `lo = max(weights)`।
2. **`d` 0 থেকে শুরু করা** — অন্তত 1 দিন লাগবেই; `d = 1` দিয়ে শুরু, নইলে দিন এক কম গোনা হয়।
3. **package ভাঙা/ক্রম বদলানো ধরে নেওয়া** — এই problem-এ ক্রম স্থির ও package অবিভাজ্য; greedy-তে সামনে থেকেই নিতে হয়।
4. **minimize move উল্টে ফেলা** — পারলে `hi = mid`, না পারলে `lo = mid+1`। (maximize-এর সাথে গুলিও না।)
5. **`cur + w > cap`-এর জায়গায় `>=` লেখা** — `>=` দিলে ঠিক capacity-পূর্ণ দিনও ভেঙে যায়, দিন বেশি গোনা হয়। `>` সঠিক।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Split Array Largest Sum** (