668. Kth Smallest Number in Multiplication Table

Description

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.

 

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.

 

Constraints:

• 1 <= m, n <= 3 * 104
• 1 <= k <= m * n

 

Solutions

Solution: Binary Search

• Time complexity: O(mlogmn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
const findKthNumber = function (m, n, k) {
  let left = 1;
  let right = m * n;

  const getSmallerCount = target => {
    let count = 0;

    for (let row = 1; row <= m; row++) {
      count += target >= row * n ? n : Math.floor(target / row);
    }
    return count;
  };

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const count = getSmallerCount(mid);

    count >= k ? (right = mid) : (left = mid + 1);
  }
  return left;
};