668.Kth Smallest Number in Multiplication Table, beats 100% with Python


  • 0
    Z

    easy Python code for 668. Kth Smallest Number in Multiplication Table, and beats 100% with 488ms runtime.
    Based on https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/discuss/, 5.solution like Kth Smallest Number in Sorted Matrix, I just improve it by asserting m <= n.

    class Solution(object):
        def findKthNumber(self, m, n, k):
            """
            :type m: int
            :type n: int
            :type k: int
            :rtype: int
            """
            def countLessThan(x, m, n):
                assert m <= n
                count = 0
                for i in xrange(1, m+1):
                    if x/i < n:
                        count += x/i
                    else:
                        count += n
                return count
            if m > n:
                m, n = n, m
            lo, hi = 1, m*n
            while lo < hi:
                mid = (lo + hi)/2
                if countLessThan(mid, m, n) < k:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

Log in to reply
 

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