Problem statement

https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/

Solution

There is bruteforce solution with O(mn) complexity, there is Heap solution, using the idea of problem 0373 Find K Pairs with Smallest Sums with complexity O(k * m log m).

Finally, there is Binary Search solution, where for number x we asking the question: how many numbers less than x we have in table: more or less than k.

Complexity

We can answer to this question in O(m), so final complexity is O(m * log(mn)$.

Code

class Solution:
    def findKthNumber(self, m, n, k):
        def lessEq(x):
            return sum([min(x//i, n) for i in range(1, m+1)]) >= k
        
        beg, end = 1, m*n
        while beg < end:
            mid = (beg + end)//2
            if not lessEq(mid):
                beg = mid + 1
            else:
                end = mid
        return beg