Kth smallest number in multiplication table

Math Binary Search

53.8% acceptance

Feb 20, 2026

2266

Given three integers m, n, and k, return the k-th smallest element in the m x n multiplication table.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_kth_number(m: i32, n: i32, k: i32) -> i32 {
    let mut lo = 1i32;
    let mut hi = m * n;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      // count elements <= mid
      let count: i32 = (1..=m).map(|i| (mid / i).min(n)).sum();
      if count >= k {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}