Kth Smallest Number in Multiplication Table

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:

1. 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.

2. 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.

• These examples illustrate how different configurations of the table affect the range and order of numbers. For each combination of m, n, and k, the product values are arranged as if serialized row-wise but need to be imagined in a flattened and sorted way to pick the kth 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

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;
    }
}