Python, Straightforward with Explanation


  • 6

    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
    

  • 0
    S

    Can you explain how does this work

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

  • 1

    @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.


  • 0
    B

    @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!


  • 0

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


  • 1
    T

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


  • 1

    @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.


Log in to reply
 

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