Description
Given an m x n multiplication table, find the kth smallest number. The table has m rows and n columns where cell (i,j) = i * j.
Examples
Input:
m = 3, n = 3, k = 5Output:
3Explanation:
Table is [[1,2,3],[2,4,6],[3,6,9]], 5th smallest is 3.
Input:
m = 2, n = 4, k = 1Output:
1Explanation:
Table is [[1,2,3,4],[2,4,6,8]]. The sorted unique values are [1,2,3,4,6,8]. The 1st smallest number is 1.
Input:
m = 4, n = 2, k = 7Output:
6Explanation:
Table is [[1,2],[2,4],[3,6],[4,8]]. The sorted unique values are [1,2,3,4,6,8]. The 7th smallest number considering all values (including duplicates from multiplication) is 6.
Constraints
- •
1 ≤ m, n ≤ 3 * 10⁴ - •
1 ≤ k ≤ m * n