Algorithm
Problem Name: 668. Kth Smallest Number in Multiplication Table
Problem Link: https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/
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 * 1041 <= k <= m * n
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findKthNumber(int m, int n, int k) {
int low = 0;
int high = m * n;
while (low < high) {
int mid = (low + high) / 2;
int count = 0;
for (int i = 1; i < = m; i++) {
count += Math.min(n, mid / i);
}
if (count >= k) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
Input
m = 3, n = 3, k = 5
Output
3
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const findKthNumber = function(m, n, k) {
let left = 1;
let right = m * n;
while (left < right) {
const mid = Math.floor((left + right) / 2);
const nSmaller = count(m, n, mid);
if (nSmaller >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
function count(m, n, target) {
let nSmaller = 0;
let j = n;
for (let i = 1; i < = m; i++) {
while (i * j > target) {
j -= 1;
}
nSmaller += j;
}
return nSmaller;
}
Input
m = 3, n = 3, k = 5
Output
3
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findKthNumber(self, m, n, k):
l, r = 1, m * n
while l < r:
mid = (l + r) // 2
if sum(min(mid // i, n) for i in range(1, m + 1)) < k:
l = mid + 1
else:
r = mid
return l
Input
m = 2, n = 3, k = 6
Output
6
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0668_KthSmallestNumberInMultiplicationTable
{
public int FindKthNumber(int m, int n, int k)
{
int lo = 1, hi = m * n;
while (lo < hi)
{
var mid = lo + (hi - lo) / 2;
if (!FindKthNumber(mid, m, n, k)) lo = mid + 1;
else hi = mid;
}
return lo;
}
private bool FindKthNumber(int x, int m, int n, int k)
{
var count = 0;
for (int i = 1; i < = m; i++)
{
count += Math.Min(n, x / i);
if (count >= k) return true;
}
return false;
}
}
}
Input
m = 2, n = 3, k = 6
Output
6