BiruLyu
9/6/2017 - 11:35 PM

668. Kth Smallest Number in Multiplication Table.java

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int low = 1, high = m * n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int cnt = countEqualLess(m, n, mid);
            if (cnt < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            
        }
        return low;
    }
    
    private int countEqualLess(int m, int n, int val) {
        int cnt = 0;
        for (int i = 1; i <= m; i++) {
            cnt += Math.min(n, val / i);
        }
        return cnt;
    }
}