364. Kth Entry of a Times Table
A teacher draws a multiplication table with m rows and n columns, where the entry in row i and column j (both starting at 1) is the product i * j. If she writes all m * n entries in a list and sorts the list from smallest to largest, equal products appear as many times as they occur in the table.
Return the k-th entry of that sorted list, counting from 1. Building the whole table is far too slow for tables with hundreds of millions of cells, so find a way to count how many entries are at most a given value x without listing them.
Example 1
- Input:
- m = 4, n = 5, k = 7
- Output:
- 4
- Explanation:
The table has rows 1 2 3 4 5, 2 4 6 8 10, 3 6 9 12 15, 4 8 12 16 20. Sorted it starts 1, 2, 2, 3, 3, 4, 4, ..., so the 7th entry is 4.
Example 2
- Input:
- m = 2, n = 3, k = 6
- Output:
- 6
- Explanation:
The table is 1 2 3 and 2 4 6, sorted 1, 2, 2, 3, 4, 6, so the 6th entry is 6.
Constraints
1 ≤ m, n ≤ 3 * 104
1 ≤ k ≤ m * n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(m log(m * n))
- Space
- O(1)