Skip to content
RED SAGSkills
hard60 ptsbinary-searchmath

K-th Entry of a Times Table

A times table has rows rows and cols columns; the entry in row i and column j (both starting at 1) is i * j.

If all rows * cols entries are written in non-decreasing order, return the k-th one (1-indexed). The table is far too large to build.

Example 1

Input: rows = 3, cols = 3, k = 5
Output: 3
Explanation: Sorted entries: 1, 2, 2, 3, 3, 4, 6, 6, 9.

Example 2

Input: rows = 2, cols = 3, k = 6
Output: 6

Constraints

  • 1 <= rows, cols <= 3 * 10^4
  • 1 <= k <= rows * cols
Hint 1

Binary search on the value: how many entries are <= x?

Hint 2

Row i contributes min(floor(x / i), cols) entries that are <= x.

Discussion 0

Join free to post in the discussion.

Good practice for: Data Scientist, Data Engineer, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Backend Developer, Game Developer

Run checks your code on 2 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.