Kth Smallest Number in Multiplication Table

Kth Smallest Number in Multiplication Table - Problem

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

Example:

For m = 3, n = 3, k = 5, the multiplication table is:

1  2  3
2  4  6
3  6  9

The sorted elements are: [1, 2, 2, 3, 3, 4, 6, 6, 9], so the 5th smallest is 3.

Input & Output

Example 1 — Basic Case

$ Input: m = 3, n = 3, k = 5

› Output: 3

💡 Note: The 3×3 multiplication table is [[1,2,3],[2,4,6],[3,6,9]]. Sorted values: [1,2,2,3,3,4,6,6,9]. The 5th smallest is 3.

Example 2 — First Element

$ Input: m = 2, n = 3, k = 1

› Output: 1

💡 Note: The 2×3 table is [[1,2,3],[2,4,6]]. Sorted: [1,2,2,3,4,6]. The 1st smallest is 1.

Example 3 — Last Element

$ Input: m = 2, n = 2, k = 4

› Output: 4

💡 Note: The 2×2 table is [[1,2],[2,4]]. Sorted: [1,2,2,4]. The 4th smallest is 4.

Constraints

1 ≤ m, n ≤ 3 * 10⁴
1 ≤ k ≤ m * n

Visualization

Tap to expand

Understanding the Visualization

Input

m×n multiplication table with values i×j

Process

Find k-th smallest without generating all values

Output

Return the k-th smallest number

Key Takeaway

🎯 Key Insight: Binary search on the answer space and count elements efficiently instead of generating all values

Asked in

G Google 25 a Amazon 20 f Facebook 15

The key insight is that we don't need to generate all multiplication table values. Instead, we can binary search on the answer space and efficiently count how many elements are ≤ our guess. Best approach uses binary search on answer with O(m*log(m*n)) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(mlog(mn))	O(1)	Binary search on the possible answer values, counting elements ≤ mid
Generate All Values	O(mnlog(m*n))	O(m*n)	Generate all m*n values, sort them, return the k-th element

Binary Search on Answer — Algorithm Steps

Set search range: low=1, high=m*n
For each mid value, count elements ≤ mid using math
If count ≥ k, search left; otherwise search right
Return the final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Range

Binary search from 1 to m*n

Count Elements

For each guess, count values ≤ guess

Adjust Range

Narrow search based on count

Code -

solution.c — C

#include <stdio.h>

int countLessEqual(int x, int m, int n) {
    int count = 0;
    for (int i = 1; i <= m; i++) {
        int val = x / i;
        if (val > n) val = n;
        count += val;
    }
    return count;
}

int solution(int m, int n, int k) {
    int low = 1, high = m * n;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(mid, m, n) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    int m, n, k;
    scanf("%d", &m);
    scanf("%d", &n);
    scanf("%d", &k);
    int result = solution(m, n, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m*log(m*n))

Binary search runs log(m*n) iterations, each iteration counts in O(m) time

⚡ Linearithmic

Space Complexity

O(1)

Only use a few variables for binary search bounds and counting

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler