Let's binary search for the answer `A`

.

Say `enough(x)`

is true if and only if there are `k`

or more values in the multiplication table that are less than or equal to `x`

. Colloquially, `enough`

describes whether `x`

is large enough to be the `k-th`

value in the multiplication table.

Then (for our answer `A`

), whenever `x >= A`

, `enough(x)`

is `True`

; and whenever `x < A`

, `enough(x)`

is `False`

.

In our binary search, our loop invariant is that `enough(hi) = True`

. More specifically, if we were to apply `enough`

onto each argument in the interval `[lo, hi]`

, we would see 0 or more `False`

, followed by 1 or more `True`

. Once `lo == hi`

, we know that `enough(lo) = True`

, and it must have been the smallest such one, because `lo`

must have been `hi-1`

or `hi-2`

at some point, and `mi = hi-1`

would have been checked.

This leaves us with the task of counting how many values are less than or equal to `x`

. For each of `m`

rows, the `i`

-th row looks like `[i, 2*i, 3*i, ..., n*i]`

, and there are `min(x // i, n)`

values in that row that are less than or equal to `x`

.

```
def findKthNumber(self, m, n, k):
def enough(x):
return sum(min(x / i, n) for i in xrange(1, m+1)) >= k
lo, hi = 1, m*n
while lo < hi:
mi = (lo + hi) / 2
if not enough(mi):
lo = mi + 1
else:
hi = mi
return lo
```