Kth Smallest Number in Multiplication Table — Hard Problem & Solution

Problem statement

An m × n multiplication table has table[i][j] = i · j for 1 <= i <= m and 1 <= j <= n.

Return the k-th smallest entry, counting duplicates.

Example 1

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: Sorted, the table reads 1, 2, 2, 3, 3, 4, 6, 6, 9.

Example 2

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The table reads 1, 2, 2, 3, 4, 6.

Example 3

Input: m = 1, n = 1, k = 1
Output: 1

Constraints

• 1 <= m, n <= 30000
• 1 <= k <= m · n

How to solve Kth Smallest Number in Multiplication Table

Binary search over the value rather than the table. Counting entries at most x is a one-pass formula over the rows, and the count is non-decreasing in x, so the boundary where it first reaches k is the answer.

Approach

1. countLE(x): sum min(n, floor(x / i)) for i from 1 to m — row i holds the multiples of i, capped at n columns.
2. Binary search the smallest x in [1, m · n] with countLE(x) >= k.

Why it works

Row i contains i, 2i, …, ni, of which exactly floor(x / i) are at most x before the column cap applies. The count is monotone in x, and the boundary value is genuinely present in the table: the count strictly increases only at values that appear, so the first x reaching k is one of them.

Complexity

• Time — O(m log(m · n))
• Space — O(1)

Pitfalls

• m · n reaches 9 · 10^8, which fits int but leaves no room for a careless lo + hi.
• Forgetting the min(n, …) cap counts entries past the end of the row.
• The answer is a table value, not a count — returning k or the count is a common slip.

Reference solution

Python

def findKthNumber(m: int, n: int, k: int) -> int:
    def count_le(x: int) -> int:
        return sum(min(n, x // i) for i in range(1, m + 1))

    lo, hi = 1, m * n
    while lo < hi:
        mid = (lo + hi) // 2
        if count_le(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var findKthNumber = function(m, n, k) {
    var countLE = function(x) {
        var c = 0;
        for (var i = 1; i <= m; i++) c += Math.min(n, Math.floor(x / i));
        return c;
    };
    var lo = 1, hi = m * n;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (countLE(mid) >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Count Ways to Make Array With Product Hard
• Count the Number of Ideal Arrays Hard
• Number of Ways to Rearrange Sticks With K Sticks Visible Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Minimum Replacements to Sort the Array Hard