Kth Smallest in Multiplication Table
Mahabharata — Drona's Rank Table — Finding the kth Entry in the Product Matrix
m×n गुणन तालिका में k-वां लघुतम। प्रत्येक पंक्ति में ≤ mid: min(mid/i, n) — सरल गणना॥
*kth smallest in m×n multiplication table. For each row: count ≤ mid = min(mid/i, n) — simple calculation.*
The Story
In an m×n multiplication table, `table[i][j] = i * j` (1-indexed). Find the kth smallest element.
For m=3, n=3, k=5: table is [[1,2,3],[2,4,6],[3,6,9]]. Sorted: [1,2,2,3,3,4,6,6,9]. 5th = 3.
**Binary search on VALUE:** - lo=1, hi=m*n (range of possible values) - For each mid: count of elements ≤ mid in the table - Row i contains values i,2i,3i,...,ni. Count of these ≤ mid = floor(mid/i) (but at most n) - Total count = sum over rows 1..m of min(floor(mid/i), n)
```java int countLeq(int m, int n, int mid) { int count = 0; for (int i=1; i<=m; i++) count += Math.min(mid/i, n); return count; } ```
The multiplication table is row+column sorted — like a special case of bs-21, but with the count function computable without explicit storage.
The elegance: no matrix is ever built. Just row-by-row counting, exploiting the multiplicative structure.
The Full Table Builder
Build the table, sort, return kth. O(mn log(mn)) space and time.
public int findKthNumberBruteForce(int m, int n, int k) {
List<Integer> list = new ArrayList<>();
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) list.add(i*j);
Collections.sort(list);
return list.get(k-1);
}Drona's Multiplicative Count Wisdom
public int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = 0;
for (int i = 1; i <= m; i++) count += Math.min(mid / i, n);
if (count >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}Step-by-Step Walkthrough
m=2,n=3,k=6 (table: 1,2,3,2,4,6 → sorted 1,2,2,3,4,6 → 6th=6) lo=1,hi=6 mid=3: min(3/1,3)+min(3/2,3)=3+1=4<6→lo=4 mid=5: min(5/1,3)+min(5/2,3)=3+2=5<6→lo=6 lo==hi=6→return 6 ✅
Deep Insight
**Why `min(mid/i, n)`?** Row i has values i, 2i, 3i,..., n*i. Those ≤ mid: floor(mid/i) of them. But row i only has n elements (j goes 1 to n). So the count is capped at n.
**Why lo is a valid table entry:** At convergence, count(lo-1) < k ≤ count(lo). Since count is computed from a valid multiplication table, lo must equal some i*j (it's actually achievable).
**Pattern:** Binary search on value + O(m) count function = O(m log(mn)) total. Same idea as bs-21 but the count function exploits the multiplication structure.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(mn log mn) | O(mn) | Build + sort full table |
| Optimal | O(m log(mn)) | O(1) | Binary search + O(m) count per step |
Pattern Recognition
✅ kth smallest in m×n multiplication table ✅ Binary search on value [1, m*n] ✅ Count ≤ mid = sum(min(mid/i, n)) for i=1..m ✅ No explicit table construction needed **LeetCode Trigger Phrases:** → "kth smallest in multiplication table" → Virtual matrix with implicit formula → Count function exploiting structure
Bhagavad Gita 7.19
बहूनां जन्मनामन्ते ज्ञानवान्मां प्रपद्यते। वासुदेवः सर्वमिति स महात्मा सुदुर्लभः॥
At the end of many births, the wise one surrenders to Me, realizing Vasudeva is all. Such a great soul is very rare.
Connection: The multiplication table contains all products — every combination of 1 through m and 1 through n. The kth smallest is a single value hidden within this infinite-seeming grid. Binary search finds it without building the table by using the multiplicative structure — the same way a wise soul finds the divine not by exhaustively searching all of creation but by understanding the underlying principle (min(mid/i, n)) that makes counting possible without enumeration.