Approach: Binary Search on the Answer ValueYou can’t jump straight to the k-th smallest value, but given a candidate“x”, you can count in O(m) how many entries are ≤ x. Row“i” holds“i, 2i, 3i, …, n·i”, so the entries ≤ x in that row number“min(n, x / i)”. Sum over all rows.“count(x)” is monotonically non-decreasing, so binary search for the smallest x with count(x) ≥ k — that’s exactly the k-th smallest entry.impl Solution {pub fn find_kth_number(m: i32, n: i32, k: i32) - i32 {// Makemthe smaller dimension so the counting loop is as short as possible.let (m, n) if m n { (m, n) } else { (n, m) };let k k as i64;// Number of entries in the multiplication table that are x. let count_le |x: i64| - i64 { let (m, n) (m as i64, n as i64); let mut cnt: i64 0; for i in 1..m { cnt (x / i).min(n); if cnt k { break; // early exit: we only need to know whether cnt k } } cnt }; let mut lo: i64 1; let mut hi: i64 m as i64 * n as i64; // Standard lower_bound: find the smallest x with count_le(x) k. while lo hi { let mid lo (hi - lo) / 2; if count_le(mid) k { hi mid; } else { lo mid 1; } } lo as i32 }}Key detailsSwap“m”/“n” so the per-iteration loop runs only“min(m, n)” times.“i64” throughout.“m * n” can reach“3 * 10^4 * 3 * 10^4 9 * 10^8”, which fits in“i32”, but“m*n” and intermediate sums are safest in“i64”;“lo (hi - lo) / 2” also avoids any overflow habit.Early“break” once“cnt k” — the function is only used to compare against“k”, so the exact count above“k” is irrelevant.“while lo hi” with“hi mid” is the lower-bound template: on exit“lo hi” is the answer, no extra handling needed.If your judge doesn’t wrap in“impl Solution”, drop the two outer lines and use“pub fn find_kth_number(m: i32, n: i32, k: i32) - i32” as a free function.ComplexityTime: O(m · log(m·n)), with m min(m, n)Space: O(1)The counting logic is identical to the Python version I verified against brute force for all“m, n ≤ 12” and every valid“k” (zero mismatches), and it reproduces the official cases:“(3,3,5) → 3”,“(2,3,6) → 6”,“(42,34,401) → 126”.