668. Kth Smallest Number in Multiplication Table

Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).

Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.

c++

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int lo = 0, hi = m * n + 1;
        int res = INT_MAX;
        while(lo <= hi) {
            int mi = lo + (hi - lo) / 2;
            int count = getCount(mi, m, n);
            
            if(count >= k) res = min(res,mi);
            
            if(count < k) lo = mi + 1;
            else hi = mi - 1;
        }
        return res;
    }
    int getCount(int value, int m, int n) {
        int res = 0;
        for(int i = 1; i <= m; i++) {
            res += min(value / i, n);
        }
        return res;
    }
};