K-th Entry of a Times Table
HardBinary Search
Problem
Picture an m × n times table: the cell in row i and column j (both starting at 1) holds i * j. If you wrote all m * n cells in non-decreasing order, which value would be in position k (1-based)?
The table is far too big to build: m and n can each be 3 · 10^4.
Example 1
- Input:
- m = 3, n = 4, k = 7
- Output:
- 4
The cells sorted are 1, 2, 2, 3, 3, 4, 4, 6, 6, 8, 9, 12; the 7th is 4.
Example 2
- Input:
- m = 2, n = 5, k = 10
- Output:
- 10
k = m · n asks for the largest cell, 2 · 5.
Example 3
- Input:
- m = 1, n = 1, k = 1
- Output:
- 1
Constraints
- 1 ≤ m, n ≤ 3 · 10^4
- 1 ≤ k ≤ m · n
Hint
Show the first hint
Building and sorting 9 · 10^8 cells is impossible. Instead, can you count how many cells are ≤ some value x?
Walkthrough
How to approach it
01Clarify before coding
- Is k 1-based? Yes: k = 1 is the smallest cell.
- Duplicates count separately? Yes, the 2 in row 1 and the 2 in row 2 are two entries.
- Do I need the position of the cell? No, just its value.
02Brute force
Generate all m·n products, sort them and take index k - 1. A heap that pops k times is the classic improvement.
Cost: Sorting is O(mn log(mn)) time and O(mn) memory (9 · 10^8 values); the heap is O(k log m), still up to 10^10.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.