The k-th smallest entry of a multiplication table
The m × n multiplication table has the value i × j in row i and column j
(both counted from 1). Return the k-th smallest value in the table, counting repeats. The table has up to
9 × 10⁸ cells, so it cannot be built.
Examples
| Input | Output | Why |
|---|---|---|
m = 3, n = 3, k = 5 | 3 | Values in order: 1, 2, 2, 3, 3, 4, 6, 6, 9. |
m = 2, n = 3, k = 6 | 6 |
Constraints
- 1 ≤ m, n ≤ 3 × 10⁴
- 1 ≤ k ≤ m × n
Hints
Hint 1
Building and sorting the table is out of the question. What can you compute quickly for a given value x?
Hint 2
Row i is i, 2i, 3i, …, n·i. How many of those are ≤ x?
Hint 3
min(⌊x / i⌋, n). Sum over the rows to get count(x) in O(m), then find the smallest x with count(x) ≥ k.
Where people lose marks
- Forgetting the cap at n: row 1 has n entries, not x of them.
- Returning the first x whose count equals k: with repeats the count can jump past k without equalling it.
- Computing m × n in 32 bits: up to 9 × 10⁸ fits, but only just; use 64 bits for the bound and the count.
Dry run on 4,5,11
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7k11
The 4 × 5 table, drawn only to show the counts. Values run from 1 to 20.
-
Step 2 / 7lo1mid10hi20count15
count(10) = min(10/1, 5) + min(10/2, 5) + min(10/3, 5) + min(10/4, 5) = 5 + 5 + 3 + 2 = 15. At least 11: hi = 10.
-
Step 3 / 7lo1mid5hi10count9
count(5) = min(5/1, 5) + min(5/2, 5) + min(5/3, 5) + min(5/4, 5) = 5 + 2 + 1 + 1 = 9. Fewer than 11: lo = 6.
-
Step 4 / 7lo6mid8hi10count13
count(8) = min(8/1, 5) + min(8/2, 5) + min(8/3, 5) + min(8/4, 5) = 5 + 4 + 2 + 2 = 13. At least 11: hi = 8.
-
Step 5 / 7lo6mid7hi8count11
count(7) = min(7/1, 5) + min(7/2, 5) + min(7/3, 5) + min(7/4, 5) = 5 + 3 + 2 + 1 = 11. At least 11: hi = 7.
-
Step 6 / 7lo6mid6hi7count11
count(6) = min(6/1, 5) + min(6/2, 5) + min(6/3, 5) + min(6/4, 5) = 5 + 3 + 2 + 1 = 11. At least 11: hi = 6.
-
Step 7 / 7answer6
lo = hi = 6: count(6) = 11 ≥ 11 and count(5) = 9 < 11. The answer is 6.
How to think about it
This is the previous problem's method with a much faster count. Row i of the table is the
multiples i, 2i, …, n·i, so the number of its entries that are ≤ x is
min(⌊x / i⌋, n), and
count(x) = Σi=1..m min(⌊x / i⌋, n)
in O(m) without looking at a single cell. The k-th smallest value is the smallest x with
count(x) ≥ k, so binary search x over [1, m·n].
The search tests numbers like 7 that may not be in the table at all (no product of two small numbers is a large prime). That does no harm: the first value whose count reaches k is always a table value, because the count only changes at table values.
Cost: O(m log(mn)), about 30 × 3 × 10⁴ operations at the largest sizes. Looping over the smaller of
m and n makes it O(min(m, n) log(mn)).
Complexity. Time O(m log(mn)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def kth_in_table(m, n, k):
def count_at_most(x): # row i holds i, 2i, ..., n*i
return sum(min(x // i, n) for i in range(1, m + 1))
lo, hi = 1, m * n
while lo < hi:
mid = (lo + hi) // 2
if count_at_most(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo#include <algorithm>
long long solve(long long m, long long n, long long k) {
auto countAtMost = [&](long long x) { // row i holds i, 2i, ..., n*i
long long c = 0;
for (long long i = 1; i <= m; ++i) c += std::min(x / i, n);
return c;
};
long long lo = 1, hi = m * n;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (countAtMost(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
public int kthInTable(int m, int n, int k) {
long lo = 1, hi = (long) m * n;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
long c = 0;
for (int i = 1; i <= m; i++) c += Math.min(mid / i, n); // row i: i, 2i, ..., n*i
if (c >= k) hi = mid; else lo = mid + 1;
}
return (int) lo;
}
}function kthInTable(m, n, k) {
const countAtMost = x => { // row i holds i, 2i, ..., n*i
let c = 0;
for (let i = 1; i <= m; i++) c += Math.min(Math.floor(x / i), n);
return c;
};
let lo = 1, hi = m * n;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (countAtMost(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
}fn solve(m: i64, n: i64, k: i64) -> i64 {
let count_at_most = |x: i64| -> i64 { (1..=m).map(|i| (x / i).min(n)).sum() }; // row i: i, 2i, ..., n*i
let (mut lo, mut hi) = (1i64, m * n);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if count_at_most(mid) >= k { hi = mid } else { lo = mid + 1 }
}
lo
}solve :: Int -> Int -> Int -> Int
solve m n k = go 1 (m * n)
where
countAtMost x = sum [min (x `div` i) n | i <- [1 .. m]] -- row i: i, 2i, ..., n*i
go lo hi
| lo >= hi = lo
| countAtMost mid >= k = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- The k-th smallest of all pairwise products a[i] × b[j] of two sorted positive arrays: count with two pointers per x.
- The k-th smallest fraction p / q among primes: the same search over real values, counting with two pointers.
Next problems
The k-th smallest value in a sorted matrix
Search over values, not positions: count the cells ≤ x with a staircase walk in O(n), and find the smallest x whose count reaches k.
Open the problem → Hard30 minThe k-th smallest distance between two values
There are n²/2 distances, too many to sort. Sort the values, count pairs within distance d by sliding window, and search for the first d whose count reaches k.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
The k-th smallest value in a sorted matrix
Search over values, not positions: count the cells ≤ x with a staircase walk in O(n), and find the smallest x whose count reaches k.
Open the problem → Hard30 minThe k-th smallest distance between two values
There are n²/2 distances, too many to sort. Sort the values, count pairs within distance d by sliding window, and search for the first d whose count reaches k.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.