Funcia
Lv.2binary-searchmathparametric-search

K-th Smallest in a Multiplication Table

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

An m × n multiplication table has i × j in row i, column j (1≤i≤m1 \le i \le m, 1≤j≤n1 \le j \le n). Return the k-th smallest of its m×nm \times n entries (equal values in different cells are counted separately).

Examples

mnkresult
3353
2366
1111

Example 1 — Sorted entries: 1, 2, 2, 3, 3, 4, 6, 6, 9; the 5th is 3.

Example 2 — 1, 2, 2, 3, 4, 6; the 6th is 6.

Example 3 — A single cell.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(m: int, n: int, k: int) → int

Constraints

  • 1≤1 \le m, n ≤30,000\le 30{,}000
  • 1≤1 \le k ≤m×n\le m \times n

Expected complexity

Time
O(m log(mn))
Space
O(1)

Examples

mnkExpected
3353
2366
1111

Hint

Hint

Do not build or heap-walk the table (up to 9⋅1089 \cdot 10^8 cells). Count instead: row i has min(n, ⌊x/i⌋) entries ≤ x, so count(x) takes O(m)O(m). It is non-decreasing in x, so binary search the smallest x in [1, m·n] with count(x) ≥ k. Total O(mlog⁡(mn))O(m \log(mn)).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.