782. The kth Entry of the Times Table
Consider the m by n multiplication table, where the entry in row i and column j is
i * j, with both counted from 1. Print the kth smallest of its m * n entries, counting
duplicates separately.
3 3 5 -> 3 table 1 2 3 / 2 4 6 / 3 6 9, sorted 1 2 2 3 3 4 6 6 9
2 3 6 -> 6 table 1 2 3 / 2 4 6, sorted 1 2 2 3 4 6
1 9 4 -> 4 one row, so the table IS 1..9
10 10 50 -> 24
## The table is never built
m and n reach 50000, so the table holds 2.5 * 10^9 entries. Writing them down is out of
the question in both time and memory, and yet the kth smallest is perfectly well defined. This
is the clearest case in the block of searching a multiset that does not exist anywhere.
## Counting entries at most x, one row at a time
Row i holds i, 2i, 3i, ... , n i. The ones at most x are those with j <= x / i, and j
cannot exceed n, so row i contributes
min(n, x / i) integer division
and the whole table contributes the sum of that over i = 1 .. m. One guess costs O(m).
## Why the count is monotone
Each term min(n, x / i) is non-decreasing in x, because integer division by a fixed positive
i never falls when the numerator rises, and min with a constant preserves that. A sum of
non-decreasing terms is non-decreasing.
## Why the answer is an entry that really appears
Search for the smallest x with count(x) >= k. Then count(x - 1) < k, so some entry lies in
(x - 1, x], and entries are integers, so an entry equals x. This matters here more than
anywhere else in the block, because a careless search can easily return something like 7 in a
table that contains no 7 at all: with m = n = 3 the table's values are
1 2 3 4 6 9, and 5, 7 and 8 never appear.
## The bounds
lo = 1 and hi = m * n, the bottom-right corner and the largest entry. k can be as large as
m * n, in which case the answer is that corner and the search must be allowed to reach it.
## The boundary that breaks a careless implementation
min(n, x / i) must clamp at n. Dropping the clamp counts x / i entries in row i even
when that exceeds the row's length, so the count runs high, the search converges early, and the
answer comes back too small. It is invisible whenever x is small relative to n and shows up
as soon as k approaches m * n.
## Relationship with problem 780
The times table is a doubly sorted grid: i * j never falls along a row or down a column. So 780
is the same question about the same shape of data, and both find the answer as the smallest x
whose count of entries at most x reaches k.
The counters differ because the grids do. 780 is handed its values and can say nothing about a
cell until it reads that cell, so it walks the staircase from the bottom-left corner, spending one
step per row and per column. Here every row is an arithmetic progression, so a whole row is
counted by a single division, min(n, x / i), and the table itself is never stored or visited at
all.
## Overflow
m * n reaches 2.5 * 10^9, past 2^31 - 1. Both the upper bound and the running count must
be 64-bit. Stopping the row loop early once the count has already reached k is also worth
doing: it does not change the answer and it removes most of the work on small guesses.
## Cost
Time O(m log(m n)). Space O(1).
Constraints - `1 ≤ m, n ≤ 50000` - `1 ≤ k ≤ m * n`
Input
The first line contains three integers m, n and k.
Output
Print a single integer: the kth smallest entry of the m by n multiplication table.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.