Problem link ও উৎস
- **Original source:** LeetCode — Kth Smallest Number in Multiplication Table
- **Platform:** LeetCode —
(related: CSES Factory Machines —
)
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Hard
- **Pattern:** BSoA + counting (উত্তরের উপর binary search, check = "≤ x কতগুলো" গোনা)
- **Basic idea inherited from:** 096 — Minimum Eating Speed
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
ভাবো একটা `m × n` গুণফল সারণি (multiplication table) — যেখানে `i` নম্বর সারি ও `j` নম্বর কলামের ঘরে বসে `i × j` (সারি/কলাম 1 থেকে গোনা)। যেমন 3×3 table:
```text
1 2 3
1 | 1 2 3
2 | 2 4 6
3 | 3 6 9
```
এই table-এর **সব ঘর একসাথে নিয়ে sorted করলে** `k`-তম সবচেয়ে ছোট সংখ্যা কোনটা — সেটাই বের করতে হবে। উপরের 3×3 table-এর সব মান sorted: `[1, 2, 2, 3, 3, 4, 6, 6, 9]`। এর 5-তম (k=5) মান = **3**।
মনে রাখো — একই মান একাধিকবার আসতে পারে (যেমন 2 এসেছে দুবার: 1×2 আর 2×1), আর আমরা সেগুলো আলাদা গণনা করি (duplicate সহ k-তম)।
### Input ও output {#6-example-input-and-output}
```text
m n k output কেন
-----------------------------------------------------------
3 3 5 3 sorted [1,2,2,3,3,4,6,6,9]-এর 5ম
2 3 6 6 সব 6 ঘর: [1,2,2,3,4,6], 6ম = 6
1 1 1 1 একমাত্র ঘর
1 5 3 3 সারি একটাই: [1,2,3,4,5], 3য় = 3
5 1 3 3 কলাম একটাই: [1,2,3,4,5], 3য় = 3
3 3 1 1 সবচেয়ে ছোট = 1×1
3 3 9 9 সবচেয়ে বড় = 3×3
```
মূল edge case: **`k=1`** → সবসময় 1 (table-এর ক্ষুদ্রতম ঘর `1×1`); **`k = m×n`** → সবচেয়ে বড় মান `m×n`; আর **এক-সারি বা এক-কলাম** table (m=1 বা n=1) → তখন মানগুলো ঠিক `1, 2, ..., max(m,n)`, তাই উত্তর `k`।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা বিশাল লাইব্রেরিতে বইগুলো দামের ক্রমে সাজানো — কিন্তু এত বেশি বই যে গুনে গুনে k-তম সস্তা বইটা বের করা অসম্ভব। তোমার কাছে শুধু একটা চটপটে যন্ত্র আছে: যেকোনো দাম `x` বললে, সে বলে দেয় "`x` টাকার কমে বা সমান কতগুলো বই আছে" (পুরো লাইব্রেরি না ঘেঁটেই, একটা সূত্রে)।
এখন তুমি দাম নিয়ে binary search করো: একটা দাম আন্দাজ করো, যন্ত্রকে জিজ্ঞেস করো "এর কমে কয়টা?"। সংখ্যাটা `k`-এর কম হলে দাম আরও বাড়াও; `k` বা তার বেশি হলে কমাও (কিন্তু এই দামটাও সম্ভাব্য উত্তর হিসেবে রাখো)। ঠিক সেই প্রথম দাম যেখানে "এর কমে-সমান অন্তত k-টা বই" — সেটাই k-তম সস্তা বইয়ের দাম। তুমি একটাও তাক না ঘুরে, শুধু গোনার যন্ত্র দিয়ে উত্তর পেয়ে গেলে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **096 — Minimum Eating Speed (Koko)**-এর উপর। 096-এ প্রথমবার তুমি দেখেছিলে — answer space একটা array নয়, একটা সংখ্যার পরিসর (খাওয়ার গতি), আর প্রতিটা guess-এর জন্য একটা check (সব কলা সময়ে শেষ হয় কি?) চালিয়ে binary search করা যায়। এখানে হুবহু সেই কাঠামো: answer space `[1, m×n]`, আর check = "`≤ x` মান `≥ k` কিনা"।
নতুন যেটা যোগ হলো — check-টা এখন একটা **counting** (গণনা), feasibility নয়। আর উত্তর খোঁজার ধরনটা 092-এর lower bound-এর মতো ("প্রথম যেখানে শর্ত True")। তাই বলা যায় এই problem = 096-এর BSoA কাঠামো + 092-এর lower-bound চলন + একটা গণিত-counting। আটকে গেলে 096-এ ফিরে দেখো — answer-space-এর সিঁড়িটা সেখানেই পরিষ্কার হয়েছিল।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা — **binary search on the answer + counting (ফলাফলের উপর দ্বিভাজন + গণনা)**। উত্তরটা কোনো array-র index নয়, একটা **সংখ্যা** যা `[1, m×n]`-এর মধ্যে। আমরা সরাসরি k-তম মান না খুঁজে প্রশ্নটা উল্টে দিই: "একটা মান `x` ধরলে, table-এ `≤ x` কতগুলো ঘর আছে?"
মূল গাণিতিক সত্য — এই গোনা `x`-এর সাথে **monotonic** (অ-হ্রাসমান): `x` বাড়ালে `≤ x` ঘরের সংখ্যা বাড়ে বা সমান থাকে। তাই "প্রথম এমন `x` যেখানে `count(≤ x) ≥ k`" — সেটাই k-তম মান (lower-bound চিন্তা)। আর gonaটা চটপটে: সারি `i`-তে `≤ x` মান হলো `i × j ≤ x` অর্থাৎ `j ≤ x / i`, মানে ঐ সারিতে `min(x // i, n)`টা ঘর। সব সারি যোগ করলেই মোট count — পুরো table না ঘুরেই, O(m) সময়ে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — পুরো table-এর সব `m×n` মান একটা list-এ ভরো, sort করো, `k−1` index-এর মানটা পড়ো:
```python
def kth_brute(m, n, k):
vals = []
for i in range(1, m + 1):
for j in range(1, n + 1):
vals.append(i * j)
vals.sort()
return vals[k - 1]
```
একদম সোজা আর নিশ্চিত ঠিক — তাই asserts-এ এটাই reference। ছোট `m, n`-এ চমৎকার (heap দিয়ে সামান্য দ্রুত করা যায়, কিন্তু সেটাও সব মান ছোঁয়)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
table-এ মোট `m × n` ঘর — সেগুলো তৈরি করতে O(m·n), sort করতে O(m·n·log(m·n)) সময় ও O(m·n) স্মৃতি। `m = n = 30000` হলে ঘর সংখ্যা 90 কোটি — স্মৃতিতেই ধরবে না, সময়ের তো কথাই নেই।
```text
m = n = 30000 হলে:
brute (সব ঘর + sort): ~9e8 ঘর তৈরি ও sort (স্মৃতি ও সময়ে অসম্ভব)
BSoA + counting : ~log2(9e8) × m ≈ 30 × 30000 = 9e5 ধাপ (চটপট)
```
মূল অপচয় — আমরা **সব** মান তৈরি ও sort করছি, যেখানে দরকার মাত্র একটা (k-তম)। আর সারি-গঠনের সুন্দর নিয়মটা (`i×j` বাড়তে থাকে) পুরো উপেক্ষা করছি। সেই নিয়মই counting-কে O(m) করে দেয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — সব মান না বানিয়ে, **উত্তরের উপর binary search** করো, আর প্রতিটা guess `x`-এ "≤ x কতগুলো" সূত্রে গোনো:
```python
def count_leq(x, m, n):
"""table-এ <= x মানের ঘর সংখ্যা — O(m)।"""
total = 0
for i in range(1, m + 1):
total += min(x // i, n) # সারি i-তে i*j <= x => j <= x//i
return total
def kth_smallest(m, n, k):
lo, hi = 1, m * n
while lo < hi:
mid = (lo + hi) // 2
if count_leq(mid, m, n) >= k: # mid-এর ছোট-সমান অন্তত k টা
hi = mid # mid নিজেই উত্তর হতে পারে
else:
lo = mid + 1 # আরও বড় মান লাগবে
return lo
```
`log(m·n)` ধাপ, প্রতি ধাপে counting O(m) (ছোট মাত্রায় চালালে আরও ভালো)। সব মিলিয়ে O(m · log(m·n))।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **"k-তম মান কত?" সরাসরি কঠিন, কিন্তু "একটা মান `x`-এর ছোট-সমান কতগুলো আছে?" সহজ — আর সেটাই যথেষ্ট।**
কারণ "≤ x গোনা" `x`-এর সাথে monotonic, তাই একটা F...FT...T রেখা পাই: "প্রথম `x` যেখানে `count(≤ x) ≥ k`" সেটাই k-তম মান। কেন সেই `x` table-এ আসলেই আছে (gap-এ পড়ে না)? কারণ ঠিক সেই বিন্দুতে count লাফ দিয়ে `k` ছোঁয় — মানে ঐ মানের অন্তত একটা ঘর বিদ্যমান। আর সারির গঠন (`i×j`) থেকে gonaটা প্রতি সারিতে এক ভাগ (`x // i`) — পুরো table ছোঁয়ার দরকারই নেই। "k-তম ছোট/বড় খুঁজতে হবে কিন্তু সব মান বানানো অসম্ভব" দেখলেই এই "count-এর উপর binary search" মাথায় আসুক।
### ছবিতে বোঝা {#5-visual-explanation}
`m=3, n=3, k=5`। answer space `[1, 9]`। প্রতিটা `x`-এ `count(≤ x)` = সব সারিতে `min(x // i, n)`-এর যোগফল:
```text
table (i×j): count(≤ x) সূত্র: সারি i-তে min(x//i, n)
1 2 3
1 | 1 2 3 x=4: সারি1: min(4//1,3)=3
2 | 2 4 6 সারি2: min(4//2,3)=2
3 | 3 6 9 সারি3: min(4//3,3)=1 -> count = 6
sorted সব মান: 1 2 2 3 3 4 6 6 9
positions: 1 2 3 4 5 6 7 8 9
^ k=5 -> মান 3
```
F/T সিঁড়ি — predicate "count(≤ x) ≥ 5" (lower bound খুঁজছি):
```text
x: 1 2 3 4 5 6 7 8 9
count(≤x): 1 3 5 6 6 8 8 8 9
count≥5 ?: F F T T T T T T T
^
প্রথম T = x=3 -> k-তম মান = 3
```
লক্ষ করো — `count(≤ x)` কখনো কমে না (monotonic), তাই F...FT...T সাজানো রেখা; binary search প্রথম T (=3) এনে দেয়। আর এই count পুরো 9 ঘর না ঘুরে শুধু 3 সারির যোগফলে পাওয়া গেল।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`m=3, n=3, k=5`। `lo=1, hi=9`। `count_leq(x)` = `min(x//1,3) + min(x//2,3) + min(x//3,3)`:
| lo | hi | mid=(lo+hi)//2 | count_leq(mid) | count ≥ 5? | নতুন lo, hi |
| --- | --- | --- | --- | --- | --- |
| 1 | 9 | 5 | min(5,3)+min(2,3)+min(1,3)=3+2+1=6 | হ্যাঁ | hi = 5 |
| 1 | 5 | 3 | min(3,3)+min(1,3)+min(1,3)=3+1+1=5 | হ্যাঁ | hi = 3 |
| 1 | 3 | 2 | min(2,3)+min(1,3)+min(0,3)=2+1+0=3 | না | lo = 3 |
| 3 | 3 | — | lo == hi, loop থামল | — | উত্তর 3 |
শেষ অবস্থা: `lo = hi = 3`। sorted `[1,2,2,3,3,4,6,6,9]`-এর 5ম মান সত্যিই 3 — brute force-এর সাথে মিলে গেল। লক্ষ করো mid=3-এ count ঠিক 5 (= k) হলো, কিন্তু আমরা তবু `hi=mid` করে নিশ্চিত করলাম 3-এর ছোট কোনো মান k ছোঁয় না (mid=2-এ count মাত্র 3) — এটাই lower-bound-এর সূক্ষ্মতা।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def count_leq(x, m, n):
"""m×n গুণফল-সারণিতে <= x মানের ঘর সংখ্যা গোনে। O(m)।"""
total = 0
for i in range(1, m + 1):
total += min(x // i, n) # সারি i: i*j <= x <=> j <= x // i, সর্বোচ্চ n
return total
def kth_smallest(m, n, k):
"""m×n গুণফল-সারণির k-তম ক্ষুদ্রতম মান (duplicate সহ)। O(m log(m·n))।"""
lo, hi = 1, m * n # answer space: ছোটতম 1, বৃহত্তম m*n
while lo < hi:
mid = (lo + hi) // 2
if count_leq(mid, m, n) >= k: # mid-এর ছোট-সমান অন্তত k টা -> mid যথেষ্ট বড়
hi = mid # mid নিজেই উত্তর হতে পারে
else:
lo = mid + 1 # ছোট পড়ছে -> বড় মান চাই
return lo
def kth_brute(m, n, k):
"""সব ঘর বানিয়ে sort করে k-তম — reference (ছোট m,n)।"""
vals = [i * j for i in range(1, m + 1) for j in range(1, n + 1)]
vals.sort()
return vals[k - 1]
# --- হাতে বাছা test ---
assert kth_smallest(3, 3, 5) == 3
assert kth_smallest(2, 3, 6) == 6
assert kth_smallest(1, 1, 1) == 1
assert kth_smallest(1, 5, 3) == 3
assert kth_smallest(5, 1, 3) == 3
assert kth_smallest(3, 3, 1) == 1
assert kth_smallest(3, 3, 9) == 9
# --- brute force-এর সাথে cross-check (সব m,n,k সমন্বয়) ---
for m in range(1, 9):
for n in range(1, 9):
for k in range(1, m * n + 1):
assert kth_smallest(m, n, k) == kth_brute(m, n, k), (m, n, k)
print(kth_smallest(3, 3, 5)) # 3
print(kth_smallest(2, 3, 6)) # 6
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def count_leq(x, m, n):
total = 0
for i in range(1, m + 1):
total += min(x // i, n)
```
সারি `i`-তে ঘরগুলো `i×1, i×2, ..., i×n`। এদের মধ্যে `≤ x` হলো যাদের `i×j ≤ x`, অর্থাৎ `j ≤ x / i`, পূর্ণসংখ্যায় `j ≤ x // i`। কিন্তু `j` সর্বোচ্চ `n`, তাই ঐ সারির গণনা = `min(x // i, n)`। সব সারি যোগ করলে মোট `≤ x` ঘর — পুরো table না ঘুরেই O(m)-এ।
```text
lo, hi = 1, m * n
```
answer space। ক্ষুদ্রতম মান `1×1 = 1`, বৃহত্তম `m×n`। উত্তর এই বন্ধ পরিসরে আছেই।
```text
if count_leq(mid, m, n) >= k: hi = mid else: lo = mid + 1
```
lower-bound চলন: `mid`-এর ছোট-সমান অন্তত `k` ঘর থাকলে — `mid` যথেষ্ট বড়, তবে নিজেও উত্তর হতে পারে, তাই `hi = mid` (বাদ দিই না)। কম থাকলে — আরও বড় মান লাগবে, `lo = mid + 1`। `lo == hi`-তে loop থামে; সেই মানই প্রথম যেখানে গণনা `k` ছোঁয় = k-তম মান।
cross-check অংশে সব `m, n ∈ [1,8]` ও বৈধ `k`-এর জন্য BSoA আর সম্পূর্ণ-sort brute মিলিয়ে দেখা (শত শত কেস) — সব মিললে তবেই `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
3
6
সব test pass!
```
প্রথম লাইন: `m=3, n=3, k=5` → dry run-এ পাওয়া 3। দ্বিতীয়: `m=2, n=3, k=6` → সব 6 ঘর sorted `[1,2,2,3,4,6]`, 6ম = 6। তার আগের সব `assert` (হাতে বাছা + সব ছোট `(m,n,k)` সমন্বয়ের exhaustive cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — counting+BSoA প্রতিটা কেসে brute-এর সাথে মিলেছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(m · log(m·n))** — answer space `[1, m·n]`-এ binary search, ধাপ সংখ্যা `log(m·n)`। প্রতি ধাপে `count_leq` সারি ধরে O(m) (ছোট মাত্রায় চালালে — `min(m, n)`-এ — আরও ভালো)। তাই মোট O(m log(m·n))। (brute-এর O(m·n·log(m·n)) থেকে বিশাল সাশ্রয়, কারণ আর সব ঘর ছুঁই না।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — `count_leq`-এ শুধু `total`, `i`; binary search-এ `lo, hi, mid`। কোনো বাড়তি array বা table লাগছে না। input ছাড়া স্মৃতি ধ্রুবক। (brute reference-এ `m·n` মান রাখতে O(m·n) লাগে, কিন্তু আসল সমাধান O(1)।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **পুরো table বানানোর চেষ্টা** — বড় `m, n`-এ স্মৃতি ও সময়ে অসম্ভব; গোনা সূত্রে (`x // i`) সারি ধরে করো, ঘর তৈরি কোরো না।
2. **counting-এ `min(_, n)` ভুলে যাওয়া** — `x // i` কখনো `n` ছাড়িয়ে গেলে ঐ সারিতে n-এর বেশি ঘর গোনা হবে; সর্বোচ্চ `n`, তাই `min(x // i, n)`।
3. **strict vs non-strict গুলিয়ে ফেলা** — গুনতে হবে `≤ x` (non-strict)। `< x` গুনলে duplicate-সহ k-তম ভুল আসবে।
4. **maximize move লিখে ফেলা** — এটা "প্রথম যেখানে count ≥ k" (lower bound); সন্তুষ্ট হলে `hi = mid`, `lo = mid` নয় (নইলে infinite loop)।
5. **answer space ভুল** — `lo = 0` দিলে অপ্রয়োজনীয়, `hi = max(m,n)` দিলে কম পড়ে যাবে; সঠিক পরিসর `[1, m·n]`।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Kth Smallest Element in a Sorted Matrix** (