668. Kth Smallest Number in Multiplication Table LeetCode Solution
In this guide, you will get 668. Kth Smallest Number in Multiplication Table LeetCode Solution with the best time and space complexity. The solution to Kth Smallest Number in Multiplication Table problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 * 104
1 <= k <= m * n
Complexity Analysis
Time Complexity: O(m\log mn)
Space Complexity: O(1)
668. Kth Smallest Number in Multiplication Table LeetCode Solution in C++
class Solution {
public:
int findKthNumber(int m, int n, int k) {
int l = 1;
int r = m * n;
auto numsNoGreaterThan = [&](int target) {
int count = 0;
// For each row i, count the number of numbers <= target.
for (int i = 1; i <= m; ++i)
count += min(target / i, n);
return count;
};
while (l < r) {
const int mid = (l + r) / 2;
if (numsNoGreaterThan(mid) >= k)
r = mid;
else
l = mid + 1;
}
return l;
}
}; /* code provided by PROGIEZ */
668. Kth Smallest Number in Multiplication Table LeetCode Solution in Java
class Solution {
public int findKthNumber(int m, int n, int k) {
int l = 1;
int r = m * n;
while (l < r) {
final int mid = (l + r) / 2;
if (numsNoGreaterThan(m, n, mid) >= k)
r = mid;
else
l = mid + 1;
}
return l;
}
private int numsNoGreaterThan(int m, int n, int target) {
int count = 0;
// For each row i, count the number of numbers <= target.
for (int i = 1; i <= m; ++i)
count += Math.min(target / i, n);
return count;
}
} // code provided by PROGIEZ
668. Kth Smallest Number in Multiplication Table LeetCode Solution in Python
