LeetCode-in-Java

668. Kth Smallest Number in Multiplication Table

Hard

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

Example 1:

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

Output: 3

Explanation: The 5^th smallest number is 3.

Example 2:

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

Output: 6

Explanation: The 6^th smallest number is 6.

Constraints:

• 1 <= m, n <= 3 * 104
• 1 <= k <= m * n

Solution

public class Solution {
    public int findKthNumber(int m, int n, int k) {
        int lo = 1;
        int hi = m * n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int col = n;
            int row = 1;
            int count = 0;
            while (row <= m && col >= 1) {
                int val = row * col;
                if (val > mid) {
                    col--;
                } else {
                    count += col;
                    row++;
                }
            }
            if (count < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

This site is open source. Improve this page.