Kth Smallest Number in Multiplication Table

Hard
833.

Kth Smallest Number in Multiplication Table

Kth Smallest Number in Multiplication Table is a hard coding problem on math and binary search, asked in Amazon, Google and Apple interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(m, n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Smallest Number in Multiplication Table — Solution

Kth Smallest Number in Multiplication Table solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Kth Smallest Number in Multiplication Table is a hard coding problem on math and binary search, asked in Amazon, Google and Apple interviews.

  • Difficulty: Hard
  • Topics: Math, Binary Search
  • Asked at: Amazon, Google, Apple
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Kth Smallest Number in Multiplication Table

  1. Hint 1

    Materialising m · n entries is up to 9 · 10^8 numbers — far too many to sort.

  2. Hint 2

    Binary search the value: how many entries are at most x?

  3. Hint 3

    Row i contributes min(n, floor(x / i)) entries at most x.

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

Java

private static long countTableLE(int m, int n, int x) {
    long c = 0;
    for (int i = 1; i <= m; i++) c += Math.min(n, x / i);
    return c;
}

public static int findKthNumber(int m, int n, int k) {
    int lo = 1, hi = m * n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countTableLE(m, n, mid) >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
}

C++

static long long countTableLE(int m, int n, int x) {
    long long c = 0;
    for (int i = 1; i <= m; i++) c += min(n, x / i);
    return c;
}

int findKthNumber(int m, int n, int k) {
    int lo = 1, hi = m * n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countTableLE(m, n, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search