Kth Smallest Number in Multiplication Table
Problem
Return the k-th smallest entry of the m × n multiplication table.
m=3 n=3 k=53def find_kth_number(m, n, k):
def count(v): return sum(min(v // i, n) for i in range(1, m + 1))
lo, hi = 1, m * n
while lo < hi:
mid = (lo + hi) // 2
if count(mid) < k: lo = mid + 1
else: hi = mid
return lofunction findKthNumber(m, n, k) {
const count = v => { let s = 0; for (let i = 1; i <= m; i++) s += Math.min(Math.floor(v / i), n); return s; };
let lo = 1, hi = m * n;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (count(mid) < k) lo = mid + 1; else hi = mid;
}
return lo;
}int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mid = (lo + hi) / 2, c = 0;
for (int i = 1; i <= m; i++) c += Math.min(mid / i, n);
if (c < k) lo = mid + 1; else hi = mid;
}
return lo;
}int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mid = (lo + hi) / 2, c = 0;
for (int i = 1; i <= m; i++) c += min(mid / i, n);
if (c < k) lo = mid + 1; else hi = mid;
}
return lo;
}Explanation
You could write out the whole table, sort all m·n numbers, and pick the k-th. That works but wastes time and memory. Instead we binary-search on the answer value itself.
The key idea: for any candidate value v, we can quickly count how many table entries are ≤ v without building the table. Row i holds the multiples i, 2i, 3i, ..., so the count of entries ≤ v in that row is min(v // i, n). Adding this over all rows gives the total count.
We binary-search v in the range [1, m*n]. If count(v) < k the answer must be larger, so we move lo up; otherwise the answer is v or smaller, so we pull hi down. The loop converges on the smallest v whose count reaches k.
Example: m=3, n=3, k=5. Try v=3: row 1 gives 3, row 2 gives 1, row 3 gives 1, total 5 which is ≥ 5. Try v=2: count is only 3, less than 5, so the answer is above 2. It settles on 3.
The counting answer is always the real table value because the smallest value whose count first reaches k is exactly the k-th smallest entry.