# 668. Kth Smallest Number in Multiplication Table
#### Difficulty: Hard
link: https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/

### 1. Binary Search
#### $O(log\ k)$ runtime, $O(1)$ space

直觀的暴力做法是列出所有數字，排序後找到第k個，但這麼做太慢。

轉換思考問題的方式，改成先猜一個數字(不一定要出現在表中)，檢查有沒有大於表內k個數字，找到滿足這個條件的最小值，便是答案。

套用Binary search模板，上下限為1到k，因為數字k一定比第k個數字還大。

再來，feasible函數需要有效率的計算表內有多少數字小於猜測的數字num。

用for迴圈一列一列看，不需要逐個元素檢查，因為每一列的每個數字都是列數 $i$ 的倍數，直接除$min(num // i, n)$就知道那一列有多少數字小於num。

##### python

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def feasible(num):
            count = 0
            for i in range(1, m + 1):
                add = min(num // i, n)
                # early stop
                if add == 0:
                    break
                count += add
                # early return
                if count >= k:
                    return True
            return False
        
        left, right = 1, k
        
        while left < right:
            mid = left + (right - left) // 2
            if feasible(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

###### tags: `leetcode`