Kth Smallest Number In Multiplication Table Problem
Description
LeetCode Problem 668.
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 k^th smallest element in the m x n multiplication table.
Example 1:
1
2
3
Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5^th smallest number is 3.
Example 2:
1
2
3
Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6^th smallest number is 6.
Constraints:
- 1 <= m, n <= 3 * 10^4
- 1 <= k <= m * n
Sample C++ Code using Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
int mid;
while (left < right) {
mid = (left + right) / 2;
int lessthanmid = 0;
int i = m, j = 1;
while (i >= 1 && j <= n) {
if (i * j <= mid) {
lessthanmid += i;
j ++;
} else {
i --;
}
}
if (lessthanmid < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};