
Problem Statement
Multiplication tables are a basic tool familiar to almost everyone, typically used in early schooling to teach arithmetic. The challenge here involves generating a multiplication table of size m x n
, where each cell in the table at position [i][j] is produced by multiplying i
and j
, considering a 1-based
index system, i.e., indexing starts from 1 instead of 0.
Given m
and n
as the dimensions of this multiplication table, and an integer k
, the task is to determine the kth
smallest number that appears in this m x n
multiplication table.
Examples
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
Approach and Intuition
- The multiplication table generates numbers by multiplying the indices of rows and columns. Understanding this structure helps us predict the numbers and their frequency of appearance in the table. For instance, some products will appear multiple times if there are multiple pairs of factors that yield the same product.
Example-Based Explanation:
Example 1
- Input is
m = 3, n = 3, k = 5
. - Constructing a 3x3 table:
- [1, 2, 3]
- [2, 4, 6]
- [3, 6, 9]
- In sorted order: 1, 2, 2, 3, 3, 4, 6, 6, 9. The 5th element here is 3.
- Output is
3
.
- Input is
Example 2
- Input is
m = 2, n = 3, k = 6
. - Constructing a 2x3 table:
- [1, 2, 3]
- [2, 4, 6]
- In sorted order: 1, 2, 2, 3, 4, 6. The 6th element here is 6.
- Output is
6
.
- Input is
- These examples illustrate how different configurations of the table affect the range and order of numbers. For each combination of
m
,n
, andk
, the product values are arranged as if serialized row-wise but need to be imagined in a flattened and sorted way to pick thekth
smallest.
Note, this problem typically requires a combination of computational geometry, matrix manipulation, and sometimes efficient search algorithms like binary search to deal with the potentially huge size of m
and n
without actually constructing large tables.
Solutions
- Java
class Solution {
public boolean isSufficient(int current, int rows, int cols, int target) {
int totalCount = 0;
for (int i = 1; i <= rows; i++) {
totalCount += Math.min(current / i, cols);
}
return totalCount >= target;
}
public int findKthNumber(int rows, int cols, int target) {
int low = 1, high = rows * cols;
while (low < high) {
int mid = low + (high - low) / 2;
if (!isSufficient(mid, rows, cols, target)) low = mid + 1;
else high = mid;
}
return low;
}
}
This Java solution addresses the challenge of finding the Kth smallest number in a multiplication table of a defined size. The code consists of two primary functions - isSufficient
and findKthNumber
.
The
isSufficient
function is responsible for determining if a given numbercurrent
is high enough such that there are at leasttarget
numbers in the multiplication table (defined byrows
xcols
) that are smaller than or equal tocurrent
. It iteratively counts how many numbers are smaller or equal to a potential candidate number by comparing it to each row up torows
.The
findKthNumber
function employs a binary search approach to efficiently find the Kth smallest number. It initializes its search range from1
torows * cols
(the maximum possible value in the table). Using the binary search methodology:- The midpoint
mid
between the currentlow
andhigh
bounds is evaluated. - The
isSufficient
function is invoked with the midpoint value to determine if there are sufficient numbers less than or equal to the midpoint in the table. - Based on the result, the function adjusts the
low
andhigh
pointers to narrow down the search space. The loop continues untillow
equalshigh
, pinpointing the Kth smallest number, which is then returned.
- The midpoint
The combination of binary search for narrowing down the potential numbers and the iterative checking via isSufficient
provides an optimized approach, ensuring that the correct Kth smallest number is found efficiently, suitable for large multiplication tables.
No comments yet.