Here, We see Kth Smallest Number in Multiplication Table LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Kth Smallest Number in Multiplication Table LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Kth Smallest Number in Multiplication Table LeetCode Solution
Table of Contents
Problem Statement
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:
![multtable1 grid](https://i0.wp.com/assets.leetcode.com/uploads/2021/05/02/multtable1-grid.jpg?w=1400&ssl=1)
Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.
Example 2:
![multtable2 grid](https://i0.wp.com/assets.leetcode.com/uploads/2021/05/02/multtable2-grid.jpg?w=1400&ssl=1)
Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6th smallest number is 6.
Kth Smallest Number in Multiplication Table LeetCode Solution C++
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int l=1, L=m*n;
while (L) {
int d=L>>1;
int x=l+d;
int y=0;
for (int a=n, b=0; a>0; --a) {
while (b<=m and a*b<=x) ++b;
y+=b-1;
}
if (y<k) {
l=x+1;
L-=d+1;
} else
L=d;
}
return l;
}
};
Code language: PHP (php)
Kth Smallest Number in Multiplication Table LeetCode Solution Java
class Solution {
public int countlessthanmid(int n ,int m, int mid){
int count=0;
int i=1;
int j =m;
while(i<=n && j>=1){
if(i*j<=mid){
count+=j;
i++;
}else{
j--;
}
}
return count;
}
public int findKthNumber(int m, int n, int k) {
int l = 1;
int h = m*n;
int mid =0;
int res = 0;
while(l<=h){
mid = l+(h-l)/2;
int count = countlessthanmid(m, n, mid);
if(count<k){
l = mid+1;
}else{
res = mid;
h = mid-1;
}
}
return res;
}
}
Code language: PHP (php)
Kth Smallest Number in Multiplication Table Solution JavaScript
var findKthNumber = function (m, n, k) {
let low = 0, high = m * n;
while (low + 1 < high) {
let mid = low + ~~((high - low) / 2);
let count = lessThanEqual(mid, m, n);
if (count >= k) high = mid;
else low = mid;
}
return high;
};
function lessThanEqual(target, rows, cols) {
let count = 0;
for (let i = 1; i <= rows; i++) {
count += Math.min(~~(target / i), cols);
}
return count;
}
Code language: JavaScript (javascript)
Kth Smallest Number in Multiplication Table Solution Python
class Solution(object):
def findKthNumber(self, m, n, k):
def enough(m, n, x, a):
cnt = 0
for i in range(1, m + 1):
cnt += min(x // i, n)
return cnt >= a
l, r = 0, m * n
while l < r:
mid = l + (r - l) // 2
if enough(m, n, mid, k):
r = mid
else:
l = mid + 1
return l
Code language: HTML, XML (xml)