Kth Smallest Number in Multiplication Table LeetCode solution in JavaScript

1
/**
2
 * @param {number} m
3
 * @param {number} n
4
 * @param {number} k
5
 * @return {number}
6
 */
7
var findKthNumber = function (m, n, k) {
8
  // lo always points to a value which is
9
  // not going to be our answer
10
  let lo = 0;
11
  let hi = m * n;
12

13
  // the loop stops when lo and hi point to two adjascent numbers
14
  // because lo is always incorrect, hi will contain our final answer
15
  while (lo + 1 < hi) {
16
    // As a general practice don't do a (lo + hi) / 2 because that
17
    // might cause integer overflow
18
    const mid = lo + Math.floor((hi - lo) / 2);
19
    const count = countLessThanEqual(mid, m, n);
20

21
    // Find the minimum mid, such that count >= k
22
    if (count >= k) {
23
      hi = mid;
24
    } else {
25
      lo = mid;
26
    }
27
  }
28
  return hi;
29
};
30

31
function countLessThanEqual(target, rows, cols) {
32
  let count = 0;
33
  // we move row by row in the multiplication table
34
  // Each row contains at max (target / rowIndex) elements less than
35
  // or equal to target. The number of cols would limit it though.
36
  for (let i = 1; i <= rows; i++) {
37
    count += Math.min(Math.floor(target / i), cols);
38
  }
39
  return count;
40
}