Let's binary search for the answer
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
enough describes whether
x is large enough to be the
k-th value in the multiplication table.
Then (for our answer
x >= A,
True; and whenever
x < A,
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
lo == hi, we know that
enough(lo) = True, and it must have been the smallest such one, because
lo must have been
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
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
After we have the count, we want to know if that count is greater than or equal to
@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.