# Python, Straightforward with Explanation

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

• Can you explain how does this work

``````    def enough(x):
return sum(min(x / i, n) for i in xrange(1, m+1)) >= k
``````

• @sha256pki Let's count how many values in the multiplication table are less than or equal to `x`. In the `i`-th row, the table looks like `[i, 2*i, 3*i, ..., n*i]`. The largest possible `k*i` that could appear is `x // i`. However, if `x` is really big, then perhaps `k > n`, so we need to actually take `min(x // i, n)`. We should take the sum of these over all such `i`.

After we have the count, we want to know if that count is greater than or equal to `k`.

• @awice Thank you for the clear solution. So looks like in your binary loop, you're searching for the minimum `mi` that works, in other words, you're not outputting `mi` as soon as `enough(mi)==true` because that `mi` may not exist in the multiplication table. My question is, how do you know the smallest `mi`, which is what you're returning, is guaranteed to be in the multiplication table? Thanks!

• @baselRus I updated OP with some more details that answer your question better.

• hi, I was wondering how did you come up with the idea of binary search?
hope to get some insight, thx in advance

• @TobeABetterMan Since m*n is 900 million, we need something faster than linear. If we are looking for things with logarithmic complexity, there are very few options.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.