277. Kth Smallest Number in Multiplication Table

HardBinary Search

Given three integers `m`, `n`, and `k`, consider the m x n multiplication table where the entry at row i, column j (both 1-indexed) is i * j. Return the k-th smallest number in this table. For example, with m = 3, n = 3, the table is: 1 2 3 2 4 6 3 6 9 Sorted: [1, 2, 2, 3, 3, 4, 6, 6, 9]. The 5th smallest number is 3.

Examples

Input: 3 3 5

Output: 3

Explanation: The 3x3 multiplication table sorted is [1,2,2,3,3,4,6,6,9]. The 5th smallest is 3.

Constraints

  • 1 <= m, n <= 3 * 10^4
  • 1 <= k <= m * n
Loading...

Run checks all cases above. Submit evaluates all test cases.