README.md

668. Kth Smallest Number in Multiplication Table

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 kth smallest element in the m x n multiplication table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6th smallest number is 6.

Constraints:

• 1 <= m, n <= 3 * 104
• 1 <= k <= m * n

Solutions (Rust)

1. Solution

impl Solution {
    pub fn find_kth_number(m: i32, n: i32, k: i32) -> i32 {
        let (mut m, mut n) = (m, n);
        let mut lo = 1;
        let mut hi = m * n;
        let mut flag = false;
        let mut count = 0;

        if m > n {
            (m, n) = (n, m);
        }

        while lo < hi {
            let mi = (lo + hi) / 2;
            flag = false;
            count = 0;

            for i in 1..=m {
                count += n.min(mi / i);
                flag |= mi % i == 0 && mi / i <= n;
            }

            if count < k {
                lo = mi + 1;
            } else {
                hi = mi;
            }
        }

        if flag {
            hi
        } else if count == k {
            (1..=m)
                .map(|i| n.min(hi / i + 1) * i)
                .filter(|&x| x > hi)
                .min()
                .unwrap()
        } else {
            (1..=m).map(|i| n.min(hi / i) * i).max().unwrap()
        }
    }
}