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.

&nbsp;
Example 1:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.


Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6th smallest number is 6.


&nbsp;
Constraints:


	1 &lt;= m, n &lt;= 3 * 104
	1 &lt;= k &lt;= m * n


class Solution:
    def numSmaller(self, x, m, n):
        res = 0
        for i in range(1, m + 1):
            res += min(x // i, n)
        return res
    
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        beg = 1
        end = m * n
        while beg < end:
            mid = (beg + end) // 2
            curr = self.numSmaller(mid, m, n)
            if curr < k:
                beg = mid + 1
            else:
                end = mid
        return beg
class Solution {
    public int findKthNumber(int m, int n, int k) {
        int lo = 1;
        int hi = m * n;
        
        while(lo < hi){
            int mid = lo + (hi - lo) / 2;
            
            if(count(mid, m, n) < k){
                lo = mid + 1;
            } else if(count(mid, m, n) >= k){
                hi = mid;
            }
        }
        return lo;
    }
    private int count(int mid, int m, int n){
        int ans = 0;
        for(int i = 1; i <= m; i++){
            int res = Math.min(mid / i, n);
            ans += res;
        }
        return ans;
    }
}
class Solution {
public:

    int findKthNumber(int m, int n, int k) {
        int high=m*n ,low=1;

        int mid=0, ans=1e9;
        while(low<=high)
        {
            mid=low+(high-low)/2;
            int temp=0;

            // for each i find the max value ,less than or equal to n , such that
            // i*j<=mid
            // add j to answer
           for(int i=1;i<=m;i++)
            temp+=min(mid/i,n);

            if(temp>=k)
            {
                ans=min(ans,mid);
                high=mid-1;
            }
            else
                low=mid+1;

        }
        return ans;
    }
};
/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(m, n, k) {
  // lo always points to a value which is
  // not going to be our answer
  let lo = 0;
  let hi = m * n;

  // the loop stops when lo and hi point to two adjascent numbers
  // because lo is always incorrect, hi will contain our final answer
  while (lo + 1 < hi) {

    // As a general practice don't do a (lo + hi) / 2 because that
    // might cause integer overflow
    const mid = lo + Math.floor((hi - lo) / 2);
    const count = countLessThanEqual(mid, m, n);

    // Find the minimum mid, such that count >= k
    if (count >= k) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  return hi;
};

function countLessThanEqual(target, rows, cols) {
  let count = 0;
  // we move row by row in the multiplication table
  // Each row contains at max (target / rowIndex) elements less than
  // or equal to target. The number of cols would limit it though.
  for (let i = 1; i <= rows; i++) {
    count += Math.min(Math.floor(target / i), cols);
  }
  return count;
}
Kth Smallest Number in Multiplication Table