# LeetCode 668: Kth Smallest Number in Multiplication Table

## Problem Restatement

We are given three integers `m`, `n`, and `k`.

Imagine an `m x n` multiplication table where each cell is:

```python
table[i][j] = i * j
```

using 1-based indexing.

We need to return the `k`th smallest number in this multiplication table.

The table may contain duplicates, and duplicates count separately.

For example, in a `3 x 3` table:

```text
1  2  3
2  4  6
3  6  9
```

the sorted values are:

```python
[1, 2, 2, 3, 3, 4, 6, 6, 9]
```

The 5th smallest value is `3`. The official statement gives this same task: return the kth smallest element in an `m x n` multiplication table.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integers `m`, `n`, and `k` |
| Output | The `k`th smallest value in the multiplication table |
| Table rule | Cell `(i, j)` contains `i * j` |
| Indexing | Rows and columns are 1-based |
| Duplicate values | Count as separate table entries |

Example function shape:

```python
def findKthNumber(m: int, n: int, k: int) -> int:
    ...
```

## Examples

Consider:

```python
m = 3
n = 3
k = 5
```

The table is:

```text
1  2  3
2  4  6
3  6  9
```

Sorted values:

```python
[1, 2, 2, 3, 3, 4, 6, 6, 9]
```

The 5th value is:

```python
3
```

So the answer is `3`.

Another example:

```python
m = 2
n = 3
k = 6
```

The table is:

```text
1  2  3
2  4  6
```

Sorted values:

```python
[1, 2, 2, 3, 4, 6]
```

The 6th value is:

```python
6
```

So the answer is `6`.

## First Thought: Build and Sort the Table

A direct solution is:

1. Generate every product `i * j`.
2. Sort all products.
3. Return the element at index `k - 1`.

This is simple, but the constraints allow `m` and `n` up to `3 * 10^4`, so the table can contain up to `9 * 10^8` entries. Building the full table is too expensive.

We need to find the value without materializing the table.

## Key Insight

We can binary search on the answer.

The smallest possible value is:

```python
1
```

The largest possible value is:

```python
m * n
```

For any candidate value `x`, we can count how many table entries are less than or equal to `x`.

If at least `k` entries are `<= x`, then the kth smallest value is at most `x`.

If fewer than `k` entries are `<= x`, then the kth smallest value is greater than `x`.

This gives a monotonic condition suitable for binary search.

## Counting Values Less Than or Equal to x

Consider row `i`.

The row contains:

```text
i, 2i, 3i, ..., n*i
```

We need to count how many of these values are `<= x`.

That count is:

```python
min(x // i, n)
```

Why?

`x // i` tells us how many multiples of `i` are at most `x`.

But the row only has `n` columns, so the count cannot exceed `n`.

Therefore, the total count is:

```python
sum(min(x // i, n) for i in range(1, m + 1))
```

This counting formula is the core of the standard solution.

## Algorithm

Use binary search over values.

1. Set `left = 1`.
2. Set `right = m * n`.
3. While `left < right`:
   - Let `mid = (left + right) // 2`.
   - Count how many table values are `<= mid`.
   - If the count is at least `k`, move `right = mid`.
   - Otherwise, move `left = mid + 1`.
4. Return `left`.

The binary search finds the smallest value `x` such that at least `k` table entries are `<= x`.

That value is exactly the kth smallest number.

## Correctness

Define `count(x)` as the number of entries in the multiplication table that are less than or equal to `x`.

As `x` increases, `count(x)` never decreases. This monotonic property allows binary search.

If `count(x) >= k`, then there are already at least `k` entries no larger than `x`, so the kth smallest value is less than or equal to `x`.

If `count(x) < k`, then fewer than `k` entries are no larger than `x`, so the kth smallest value must be greater than `x`.

The algorithm searches for the smallest value where `count(x) >= k`.

By definition, that smallest value is exactly the kth smallest element in the table.

The row-count formula is correct because row `i` contains the multiples `i, 2i, ..., n*i`, and exactly `min(x // i, n)` of them are at most `x`.

Therefore, the algorithm returns the correct kth smallest value.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(m log(mn))` | Each binary search step counts across `m` rows |
| Space | `O(1)` | Only counters and bounds are stored |

We can also iterate over the smaller dimension by swapping `m` and `n`, which gives:

```text
O(min(m, n) * log(mn))
```

## Implementation

```python
class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        if m > n:
            m, n = n, m

        def count_less_equal(x: int) -> int:
            count = 0

            for row in range(1, m + 1):
                count += min(x // row, n)

            return count

        left = 1
        right = m * n

        while left < right:
            mid = (left + right) // 2

            if count_less_equal(mid) >= k:
                right = mid
            else:
                left = mid + 1

        return left
```

## Code Explanation

We optionally swap dimensions:

```python
if m > n:
    m, n = n, m
```

This makes the counting loop run over the smaller dimension.

The helper function counts how many values are at most `x`:

```python
def count_less_equal(x: int) -> int:
```

For each row:

```python
count += min(x // row, n)
```

`x // row` counts how many multiples of `row` fit under `x`.

`n` caps that number by the row length.

The binary search range is:

```python
left = 1
right = m * n
```

At each step:

```python
mid = (left + right) // 2
```

If `mid` is large enough to cover at least `k` entries:

```python
if count_less_equal(mid) >= k:
    right = mid
```

then the answer may be `mid` or smaller.

Otherwise:

```python
left = mid + 1
```

the answer must be larger.

When the loop ends, `left` is the smallest valid value.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findKthNumber(3, 3, 5) == 3
    assert s.findKthNumber(2, 3, 6) == 6

    assert s.findKthNumber(1, 10, 7) == 7
    assert s.findKthNumber(10, 1, 7) == 7

    assert s.findKthNumber(3, 3, 1) == 1
    assert s.findKthNumber(3, 3, 9) == 9

    assert s.findKthNumber(4, 4, 8) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `m=3, n=3, k=5` | Standard example |
| `m=2, n=3, k=6` | Last element of a small table |
| Single row | Behaves like a sorted array |
| Single column | Confirms dimension swap is safe |
| `k=1` | Smallest value |
| `k=m*n` | Largest value |
| `4 x 4`, middle rank | Checks duplicate products |