All problems

Kth Smallest Number in Multiplication Table

Hard · binary search

A multiplication table has m rows and n columns. The cell in row i and column j (both counted from 1) holds the product i * j. The table is never built for you: you only get its size.

Imagine writing all m * n cell values in one list and sorting it from smallest to largest. Equal values appear once for every cell that holds them. Return the value at position k of that sorted list (counting from 1).

Examples

Example 1

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

Output: 3

The nine cells are 1, 2, 3, 2, 4, 6, 3, 6, 9. Sorted they read 1, 2, 2, 3, 3, 4, 6, 6, 9, and the fifth is 3.

Example 2

Input: m = 2, n = 3, k = 6

Output: 6

The cells are 1, 2, 3 and 2, 4, 6. Sorted: 1, 2, 2, 3, 4, 6.

Example 3

Input: m = 4, n = 4, k = 9

Output: 6

Sorted, the 16 cells begin 1, 2, 2, 3, 3, 4, 4, 4, 6, so the ninth is 6.

Constraints