This page explains Java solution to problem `Kth Smallest Number in Multiplication Table`

using `Binary Search`

algorithm.

Nearly every one have used the Multiplication Table. But could you find out the `k-th`

smallest number quickly from the multiplication table?

Given the height m and the length `n`

of a `m * n`

Multiplication Table, and a positive integer `k`

, you need to return the `k-th`

smallest number in this table.

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

Explanation: The Multiplication Table:

1 2 3

2 4 6

3 6 9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Input: m = 2, n = 3, k = 6Output: 6Explanation: The Multiplication Table:

1 2 3

2 4 6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

```
package com.vc.hard;
class KthSmallestNumberInMultiplicationTable {
public int findKthNumber(int m, int n, int k) {
int lo = 0;
int hi = m * n;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
int index = getIndex(m, n, mid);
if(index < k) lo = mid + 1;
else hi = mid - 1;
}
return lo;
}
private int getIndex(int m, int n, int number) {
int row = 1;
int col = n;
int numberIndex = 0;
while(row <= m && col > 0) {
if(row * col <= number) {
numberIndex += col;
row++;
}
else col--;
}
return numberIndex;
}
}
```

O(MN log MN)

O(1)