LeetCode in Kotlin
668. Kth Smallest Number in Multiplication Table
Hard
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 * 1041 <= k <= m * n
Solution
class Solution {
fun findKthNumber(m: Int, n: Int, k: Int): Int {
var lo = 1
var hi = m * n
while (lo < hi) {
val mid = lo + (hi - lo) / 2
var col = n
var row = 1
var count = 0
while (row <= m && col >= 1) {
val `val` = row * col
if (`val` > mid) {
col--
} else {
count += col
row++
}
}
if (count < k) {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
}