Задача: 668. Kth Smallest Number in Multiplication Table
Сложность: hard

Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).

Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n.

Пример:

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

👨‍💻 Алгоритм:

1⃣Установка границ поиска:
Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n.

2⃣Бинарный поиск:
Используйте бинарный поиск, чтобы найти k-й наименьший элемент.
Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid.

3⃣Проверка количества элементов:
Если количество элементов меньше k, увеличьте нижнюю границу (left).
Если количество элементов больше или равно k, уменьшите верхнюю границу (right).

😎 Решение:

var findKthNumber = function(m, n, k) {
    let left = 1, right = m * n;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (countLessEqual(m, n, mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

function countLessEqual(m, n, x) {
    let count = 0;
    for (let i = 1; i <= m; i++) {
        count += Math.min(Math.floor(x / i), n);
    }
    return count;
}

Ставь 👍 и забирай 📚 Базу знаний