Sponsored
Sponsored
The general idea is to use binary search to find the kth smallest element in the multiplication table. The key observation is that for a candidate number X, we can count how many numbers in the multiplication table are less than or equal to X, without constructing the entire table explicitly. Counting these numbers can be efficiently done by iterating over the rows and determining the highest multiple that does not exceed X.
Time Complexity: O(m * log(m * n))
Space Complexity: O(1)
1#include <iostream>
2#include <vector>
3
4int countLessOrEqual(int m, int n, int x) {
5 int count = 0;
6 for (int i = 1; i <= m; ++i) {
7 count += std::min(x / i, n);
8 }
9 return count;
10}
11
12int findKthNumber(int m, int n, int k) {
13 int low = 1, high = m * n;
14 while (low < high) {
15 int mid = low + (high - low) / 2;
16 if (countLessOrEqual(m, n, mid) < k)
17 low = mid + 1;
18 else
19 high = mid;
20 }
21 return low;
22}
23
24int main() {
25 int m = 3, n = 3, k = 5;
26 std::cout << findKthNumber(m, n, k) << std::endl; // Output: 3
27 return 0;
28}This C++ solution is similar to the C solution, using a binary search to find the kth smallest element. The function `countLessOrEqual` tells us how many numbers in the table are less than or equal to a given number x.
This approach uses a min-heap (priority queue) to keep track of the smallest unseen elements in the multiplication table. By continuously adding the next minimum elements from the rows, we can extract them in order until we reach the kth smallest element.
Time Complexity: O(k log m)
Space Complexity: O(m)
1#include <iostream>
2#include <queue>
3#include <vector>
4
5struct Comparator {
6 bool operator()(std::pair<int, int> &a, std::pair<int, int> &b) {
return a.first > b.first;
}
};
int findKthNumber(int m, int n, int k) {
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Comparator> minHeap;
for (int i = 1; i <= m; ++i)
minHeap.push({i, 1});
int count = 0, ans = 0;
while (!minHeap.empty() && count < k) {
auto elem = minHeap.top();
minHeap.pop();
++count;
ans = elem.first;
if (elem.second < n) {
minHeap.push({elem.first + elem.first / elem.second, elem.second + 1});
}
}
return ans;
}
int main() {
int m = 3, n = 3, k = 5;
std::cout << findKthNumber(m, n, k) << std::endl; // Output: 3
return 0;
}This C++ code uses a min-heap to track the smallest values efficiently. We insert initial multiples from each row into the heap and extract the smallest at each step, pushing the next element from the same row.