Kth Smallest Number in Multiplication Table

Intuition

Solution

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        lo = 1
        hi = m * n
        while lo != hi:
            mid = (lo + hi) // 2
            if self.count(m, n, mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

    def count(self, m, n, v):
        ans = 0
        for i in range(m):
            ans += min((v // (i + 1)), n)
        return ans