## DEV Community is a community of 642,334 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# LeetCode 668. Kth Smallest Number in Multiplication Table (javascript solution)

codingpineapple

### 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.

### Solution:

Time Complexity : O(nlog(n))
Space Complexity: O(1)

``````// Binary Search
var findKthNumber = function(m, n, k) {
// Check how many numbers per row x is greater than
function enough(x) {
let count = 0;
for (let i = 1; i <= m; i++) {
count += Math.min(Math.floor(x / i), n);
}
return count >= k;
}

let lo = 1, hi = m * n;
// Binary search template
while (lo < hi) {
let mi = lo + Math.floor((hi - lo) / 2);
if (enough(mi)) hi = mi;
else lo = mi + 1;
}
return lo;
};
``````