668. Kth Smallest Number in Multiplication Table

Description

Solution

Generally, k-th related problem could be solved by binary search to guess the right answer and verify. Once we enumerate a number, we could calculate its rank.

Another important thing we should notice is that we calculate the elements number that less equal than the target one.

Code

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int l = 1, r = m * n;
        while(l < r){
            int mid = l + (r - l)/2;
            //Analyze mid's property, factorization
            if(count_le(mid, m, n) < k){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
    }

    int count_le(int val, int m, int n){
        int cnt = 0;
        for(int i = 1; i <= m; i++){
            cnt += min(n, val / i);
        }
        return cnt;
    }
};