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)
1using System;
2
3class Solution {
4 public int CountLessOrEqual(int m, int n, int x) {
5 int count = 0;
6 for (int i = 1; i <= m; i++) {
7 count += Math.Min(x / i, n);
8 }
9 return count;
10 }
11
12 public int 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
24 static void Main(string[] args) {
25 Solution sol = new Solution();
26 Console.WriteLine(sol.FindKthNumber(3, 3, 5)); // Output: 3
27 }
28}This C# solution uses binary search to locate the kth smallest number in the multiplication table. It employs a method `CountLessOrEqual` that counts how many table values are not greater than the search midpoint.
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)
1import heapq
2
3def find_kth_number(m, n
This Python solution utilizes a min-heap to access elements of the multiplication table in increasing order. We initially fill the heap with the first multiple of each row index and continually add the next multiple for extraction.