668_Kth_Smallest_Number_in_Multiplication_Table.java

class Solution {
    // https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/solution/
    public boolean enough(int x, int m, int n, int k) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += Math.min(x / i, n);
        }
        return count >= k;
    }

    public int findKthNumber(int m, int n, int k) {
        int lo = 1, hi = m * n;
        while (lo < hi) {
            // ith row [i, 2*i, 3*i, ..., n*i]
            // for each column, k = x // i
            int mi = lo + (hi - lo) / 2;
            if (!enough(mi, m, n, k)) lo = mi + 1;
            else hi = mi;
        }
        return lo;
    }
}