> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0668-kth-smallest-number-in-multiplication-table.md).

# 0668. Kth Smallest Number in Multiplication Table

<https://leetcode.com/problems/kth-smallest-number-in-multiplication-table>

## Description

Nearly everyone has used the [Multiplication Table](https://en.wikipedia.org/wiki/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:**

![](https://assets.leetcode.com/uploads/2021/05/02/multtable1-grid.jpg)

```
**Input:** m = 3, n = 3, k = 5
**Output:** 3
**Explanation:** The 5th smallest number is 3.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/05/02/multtable2-grid.jpg)

```
**Input:** m = 2, n = 3, k = 6
**Output:** 6
**Explanation:** The 6th smallest number is 6.
```

**Constraints:**

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

## ac

```java
class Solution {
    public int findKthNumber(int m, int n, int k) {
        // edge cases

        int l = 1, r = m * n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int cnt = countLessOrEqual(m, n, mid);
            // determine k
            if (cnt < k) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    private int countLessOrEqual(int m, int n, int target) {
        // count less
        int less = 0,  c = n - 1;
        for (int r = 0; r < m; r++) {
            while (c >= 0 && (r+1) * (c+1) > target) c--;
            less += c + 1;
        }
        return less;
    }
}

/*
1) priority queue, O(k*mlogm), TLE;  2) binary search, O(m∗log(m∗n))
*/
```