## Algorithm

Problem Name: 668. Kth Smallest Number in Multiplication Table

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 5th smallest number is 3.
```

Example 2:

```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`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int findKthNumber(int m, int n, int k) {
int low = 0;
int high = m * n;
while (low < high) {
int mid = (low + high) / 2;
int count = 0;
for (int i = 1; i <= m; i++) {
count += Math.min(n, mid / i);
}
if (count >= k) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
``````
Copy The Code &

Input

cmd
m = 3, n = 3, k = 5

Output

cmd
3

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findKthNumber = function(m, n, k) {
let left = 1;
let right = m * n;
while (left < right) {
const mid = Math.floor((left + right) / 2);
const nSmaller = count(m, n, mid);
if (nSmaller >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};

function count(m, n, target) {
let nSmaller = 0;
let j = n;
for (let i = 1; i <= m; i++) {
while (i * j > target) {
j -= 1;
}
nSmaller += j;
}
return nSmaller;
}
``````
Copy The Code &

Input

cmd
m = 3, n = 3, k = 5

Output

cmd
3

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findKthNumber(self, m, n, k):
l, r = 1, m * n
while l < r:
mid = (l + r) // 2
if sum(min(mid // i, n) for i in range(1, m + 1)) < k:
l = mid + 1
else:
r = mid
return l
``````
Copy The Code &

Input

cmd
m = 2, n = 3, k = 6

Output

cmd
6

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0668_KthSmallestNumberInMultiplicationTable
{
public int FindKthNumber(int m, int n, int k)
{
int lo = 1, hi = m * n;

while (lo < hi)
{
var mid = lo + (hi - lo) / 2;
if (!FindKthNumber(mid, m, n, k)) lo = mid + 1;
else hi = mid;
}

return lo;
}

private bool FindKthNumber(int x, int m, int n, int k)
{
var count = 0;
for (int i = 1; i <= m; i++)
{
count += Math.Min(n, x / i);
if (count >= k) return true;
}

return false;
}
}
}
``````
Copy The Code &

Input

cmd
m = 2, n = 3, k = 6

Output

cmd
6