###### tags: `LeetCode` `Hard` `Binary Search`
# LeetCode #668 [Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/)
### (Hard)

幾乎每一個人都用 乘法表。但是你能在乘法表中快速找到第k小的數字嗎？

給定高度m 、寬度n 的一張 m * n的乘法表，以及正整數k，你需要返回表中第k 小的數字。

---

使用binary search, 比較整個乘法表中小於中值的數有幾個, 若大於等於k則將右值改為中值, 反之左值改為中值+1。

快速確認小於中值的樹的方法, 由於是乘法表(數字連續), 因此每一列中小於等於中值的數就是就是中值除以該行的列數。

---

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int l=1, r=m*n+1;
        while(l<r){
            int x=(l+r)/2;
            if(lex(m,n,x)>=k)r=x;
            else l=x+1;
        }
        return l;
    }
    int lex(int m, int n, int x){
        int count=0;
        for(int i=1;i<=m;i++){
            count+=min(n,x/i);//該列中小於x的數字個數即為x/i
        }
        return count;
    }
};