Kth Smallest Number in Multiplication Table

Updated on 05 June, 2025
Kth Smallest Number in Multiplication Table header image

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

  • Java
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 number current is high enough such that there are at least target numbers in the multiplication table (defined by rows x cols) that are smaller than or equal to current. It iteratively counts how many numbers are smaller or equal to a potential candidate number by comparing it to each row up to rows.

  • The findKthNumber function employs a binary search approach to efficiently find the Kth smallest number. It initializes its search range from 1 to rows * cols (the maximum possible value in the table). Using the binary search methodology:

    • The midpoint mid between the current low and high 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 and high pointers to narrow down the search space. The loop continues until low equals high, pinpointing the Kth smallest number, which is then returned.

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.

Comments

No comments yet.