JavaScript: K^th smallest number in a multiplication table

JavaScript Math: Exercise-111 with Solution

Kth Smallest in Multiplication Table

Write a JavaScript program that creates a multiplication table of size m x n using integers where 1 <= k <= m * n. Return the kth smallest element in the said multiplication table.

In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system.
The decimal multiplication table was traditionally taught as an essential part of elementary arithmetic around the world, as it lays the foundation for arithmetic operations with base-ten numbers. Many educators believe it is necessary to memorize the table up to 9 x 9.
The illustration below shows a table up to 12 x 12, which is a size commonly used nowadays in English-world schools.

Test Data:
(3,3,8) -> 6
(2,3,4) -> 3

Sample Solution:

JavaScript Code:

/**
 * Function to find the kth smallest element in the multiplication table of dimensions m x n.
 * @param {number} m - The number of rows in the multiplication table.
 * @param {number} n - The number of columns in the multiplication table.
 * @param {number} k - The kth smallest element to find.
 * @returns {number|boolean} - The kth smallest element if found, otherwise false.
 */
function test(m, n, k) {
    // If k is less than 1 or greater than the total number of elements in the multiplication table, return false
    if (k < 1 || k > m * n) return false;
    var s = 1, p = n * m;
    // Binary search to find the kth smallest element
    while (s <= p) {
        var mid = s + Math.floor((p - s) / 2);
        var t = 0;
        // Calculate the number of elements less than or equal to mid in the multiplication table
        for (i = 1; i <= m; i++) {
            t += Math.min(Math.floor(mid / i), n);
        }
        // Adjust the search range based on the value of t
        if (t >= k) {
            p = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    // Return the lower bound of the search range
    return s;
}

// Test cases
m = 3;
n = 3;
k = 8;
console.log("m = " + m + " : n = " + n + ", k = " + k);
console.log("kth smallest element in m x n multiplication table: " + test(m, n, k));
m = 2;
n = 3;
k = 4;
console.log("m = " + m + " : n = " + n + ", k = " + k);
console.log("kth smallest element in m x n multiplication table: " + test(m, n, k));

Output:

m = 3 : n = 3, k = 8
kth smallest element in m x n multiplication table: 6
m = 2 : n = 3, k = 4
kth smallest element in m x n multiplication table: 3

Flowchart:

Live Demo:

See the Pen javascript-math-exercise-111 by w3resource (@w3resource) on CodePen.

For more Practice: Solve these Related Problems:

• Write a JavaScript function that generates a multiplication table of size m x n and finds the kth smallest element using binary search.
• Write a JavaScript function that counts elements in a multiplication table to determine the kth smallest number efficiently.
• Write a JavaScript function that simulates the multiplication table and sorts the resulting elements to retrieve the kth smallest value.
• Write a JavaScript function that validates inputs for m, n, and k, handling cases where k is out of range.

Improve this sample solution and post your code through Disqus.

Previous: Sum of two square numbers equal to an integer.
Next: Maximum value swapping two digits in an integer.