0668. Kth Smallest Number in Multiplication Table
https://leetcode.com/problems/kth-smallest-number-in-multiplication-table
Description
Nearly everyone has used the Multiplication Table. The multiplication table of size m x n
is an integer matrix mat
where mat[i][j] == i * j
(1-indexed).
Given three integers m
, n
, and k
, return the kth
smallest element in the m x n
multiplication table.
Example 1:

**Input:** m = 3, n = 3, k = 5
**Output:** 3
**Explanation:** The 5th smallest number is 3.
Example 2:

**Input:** m = 2, n = 3, k = 6
**Output:** 6
**Explanation:** The 6th smallest number is 6.
Constraints:
1 <= m, n <= 3 * 104
1 <= k <= m * n
ac
class Solution {
public int findKthNumber(int m, int n, int k) {
// edge cases
int l = 1, r = m * n;
while (l < r) {
int mid = l + (r - l) / 2;
int cnt = countLessOrEqual(m, n, mid);
// determine k
if (cnt < k) l = mid + 1;
else r = mid;
}
return l;
}
private int countLessOrEqual(int m, int n, int target) {
// count less
int less = 0, c = n - 1;
for (int r = 0; r < m; r++) {
while (c >= 0 && (r+1) * (c+1) > target) c--;
less += c + 1;
}
return less;
}
}
/*
1) priority queue, O(k*mlogm), TLE; 2) binary search, O(m∗log(m∗n))
*/
Last updated
Was this helpful?