visual walkthrough
Kth Smallest Number in Multiplication Table
Counting under a formula without building the table.
The idea
You never need the table itself. For any guess v, each row i holds i, 2i, 3i, …, so exactly min(⌊v / i⌋, n) of its entries are ≤ v.
That count grows with v, so binary search the smallest v whose count reaches k.
Complexity
| approach | time | space |
|---|---|---|
| List every product | O(mn log mn) | O(mn) |
| Binary search with counting | O(m log mn) | O(1) |