K-th Value in a Times Table

Hard

A times table of size rows × cols is a grid where the cell in row i and column j holds i · j (rows and columns are numbered from 1). If you list all rows · cols values of the table in non-decreasing order, keeping repeats, which value is in position k? Positions count from 1.

Example 1

rows=2, cols=4, k=5 → 4

The table has rows 1, 2, 3, 4 and 2, 4, 6, 8. Sorted: 1, 2, 2, 3, 4, 4, 6, 8, so the fifth value is 4.

Example 2

rows=3, cols=3, k=9 → 9

The largest value in a 3 × 3 table is 3 · 3 = 9.

Example 3

rows=30000, cols=30000, k=450000000 → 168028638

Constraints

1 ≤ rows, cols ≤ 3 · 10⁴
1 ≤ k ≤ rows · cols

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Binary Search

Similar problems

A Base of All Ones Hard Factorials With Exactly K Trailing Zeros Hard N-th Multiple of Either Divisor Hard Prototype Drop Tests Hard Numbers From Working Keys Hard

Input

rows=2, cols=4, k=5

Expected

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.