# 668. 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

## Solutions

Binary search.

• class Solution {
public int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = (left + right) >>> 1;
int cnt = 0;
for (int i = 1; i <= m; ++i) {
cnt += Math.min(mid / i, n);
}
if (cnt >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}

• class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = (left + right) >> 1;
int cnt = 0;
for (int i = 1; i <= m; ++i) cnt += min(mid / i, n);
if (cnt >= k)
right = mid;
else
left = mid + 1;
}
return left;
}
};

• class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
left, right = 1, m * n
while left < right:
mid = (left + right) >> 1
cnt = 0
for i in range(1, m + 1):
cnt += min(mid // i, n)
if cnt >= k:
right = mid
else:
left = mid + 1
return left


• func findKthNumber(m int, n int, k int) int {
left, right := 1, m*n
for left < right {
mid := (left + right) >> 1
cnt := 0
for i := 1; i <= m; i++ {
cnt += min(mid/i, n)
}
if cnt >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}