102 — Kth Smallest in Multiplication Table

এই level-এর শেষ problem — আর এটা BSoA-র সবচেয়ে সুন্দর মোড় দেখায়: answer space-টা array নয়, সংখ্যার একটা পরিসর, আর check-টা হলো "এই মানের ছোট-সমান কতগুলো আছে গোনা"। 096 (Koko)-তে তুমি প্রথম array ছাড়া একটা পরিসরে search শিখেছিলে; এখানে সেই চিন্তার সাথে যুক্ত হবে একটা চটপটে counting trick — পুরো m×n table না বানিয়েই গোনা। এই counting+BSoA জুটি contest-এর অসংখ্য Hard problem-এর চাবি।

Source

• Original source: LeetCode — Kth Smallest Number in Multiplication Table
• Platform: LeetCode — https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ (related: CSES Factory Machines — https://cses.fi/problemset/task/1620)
• 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

1. Problem in simple words

ভাবো একটা m × n গুণফল সারণি (multiplication table) — যেখানে i নম্বর সারি ও j নম্বর কলামের ঘরে বসে i × j (সারি/কলাম 1 থেকে গোনা)। যেমন 3×3 table:

     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-তম)।

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) সময়ে।

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-এর সিঁড়িটা সেখানেই পরিষ্কার হয়েছিল।

4. Real-life analogy

ভাবো একটা বিশাল লাইব্রেরিতে বইগুলো দামের ক্রমে সাজানো — কিন্তু এত বেশি বই যে গুনে গুনে k-তম সস্তা বইটা বের করা অসম্ভব। তোমার কাছে শুধু একটা চটপটে যন্ত্র আছে: যেকোনো দাম x বললে, সে বলে দেয় "x টাকার কমে বা সমান কতগুলো বই আছে" (পুরো লাইব্রেরি না ঘেঁটেই, একটা সূত্রে)।

এখন তুমি দাম নিয়ে binary search করো: একটা দাম আন্দাজ করো, যন্ত্রকে জিজ্ঞেস করো "এর কমে কয়টা?"। সংখ্যাটা k-এর কম হলে দাম আরও বাড়াও; k বা তার বেশি হলে কমাও (কিন্তু এই দামটাও সম্ভাব্য উত্তর হিসেবে রাখো)। ঠিক সেই প্রথম দাম যেখানে "এর কমে-সমান অন্তত k-টা বই" — সেটাই k-তম সস্তা বইয়ের দাম। তুমি একটাও তাক না ঘুরে, শুধু গোনার যন্ত্র দিয়ে উত্তর পেয়ে গেলে।

5. Visual explanation

m=3, n=3, k=5। answer space [1, 9]। প্রতিটা x-এ count(≤ x) = সব সারিতে min(x // i, n)-এর যোগফল:

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 খুঁজছি):

 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 সারির যোগফলে পাওয়া গেল।

6. Example input and output

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।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — পুরো table-এর সব m×n মান একটা list-এ ভরো, sort করো, k−1 index-এর মানটা পড়ো:

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 কোটি — স্মৃতিতেই ধরবে না, সময়ের তো কথাই নেই।

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 কতগুলো" সূত্রে গোনো:

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" মাথায় আসুক।

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-এর সূক্ষ্মতা।

12. Python solution

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

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)-এ।

lo, hi = 1, m * n

answer space। ক্ষুদ্রতম মান 1×1 = 1, বৃহত্তম m×n। উত্তর এই বন্ধ পরিসরে আছেই।

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!।

14. Output walkthrough

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

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-এর সাথে মিলেছে।

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]।

18. Harder problems that inherit this idea

• LeetCode — Kth Smallest Element in a Sorted Matrix (https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) — হুবহু "count ≤ x-এর উপর binary search", শুধু counting-টা সারি ধরে দুই-pointer-এ।
• LeetCode — Find K-th Smallest Pair Distance (https://leetcode.com/problems/find-k-th-smallest-pair-distance/) — distance-এর উপর binary search + "≤ d কতগুলো জোড়া" গোনা।
• CSES — Factory Machines (https://cses.fi/problemset/task/1620) — "t সময়ে কয়টা পণ্য?" গোনা + সময়ের উপর binary search; একই BSoA+counting দর্শন।

19. Pattern learned

Binary search on the answer + counting (k-th value) — answer space একটা সংখ্যার পরিসর; check = "≤ x কতগুলো আছে" (monotonic গণনা); "প্রথম x যেখানে count ≥ k" = k-তম মান। বড় শিক্ষা: k-তম ছোট/বড় খুঁজতে সব মান sort করার দরকার নেই — মানের উপর binary search করে 'এর ছোট-সমান কতগুলো' গোনো, আর গঠন থাকলে সেই গোনা সূত্রে দ্রুত হয়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Kth in Multiplication Table = BSoA on value + counting; answer space [1, m·n], count(≤ x) = Σ min(x//i, n), 'প্রথম x যেখানে count ≥ k' = উত্তর (lower bound, sat → hi=mid)। Signal: 'k-তম ছোট, কিন্তু সব মান বানানো অসম্ভব' দেখলেই count-এর উপর binary search মনে পড়ুক।"

পরের ধাপ → এই level সম্পূর্ণ; এবার ../../08-greedy-math-tricks/problems/README.md। ভিত্তি → 096 — Minimum Eating Speed। সম্পর্কিত → 101 — Median of Two Sorted Arrays।

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

---

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