Code Implementation

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def countLessEqual(x):
            count = 0
            for i in range(1, m+1):
                count += min(x // i, n)
            return count

        left, right = 1, m * n
        while left < right:
            mid = (left + right) // 2
            if countLessEqual(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left
      

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        auto countLessEqual = [&](int x) {
            int count = 0;
            for (int i = 1; i <= m; ++i) {
                count += std::min(x / i, n);
            }
            return count;
        };

        int left = 1, right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (countLessEqual(mid) < k)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
};
      

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int i = 1; i <= m; ++i) {
                count += Math.min(mid / i, n);
            }
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
      

var findKthNumber = function(m, n, k) {
    function countLessEqual(x) {
        let count = 0;
        for (let i = 1; i <= m; ++i) {
            count += Math.min(Math.floor(x / i), n);
        }
        return count;
    }

    let left = 1, right = m * n;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (countLessEqual(mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};
      

Problem Description

Given two integers m and n, representing the number of rows and columns in a multiplication table (where the value at cell (i, j) is i * j), and an integer k, your task is to find the kth smallest number in this m x n multiplication table.

• Each number in the table is the product of a row index and a column index (both starting from 1).
• There is exactly one valid answer for each input.
• Do not generate or reuse elements outside the multiplication table.

For example, if m = 3, n = 3, and k = 5, the multiplication table is:

1 2 3
2 4 6
3 6 9
  

The sorted order of elements is [1, 2, 2, 3, 3, 4, 6, 6, 9], so the 5th smallest is 3.

Thought Process

At first glance, the problem seems to suggest building the entire multiplication table, sorting all its elements, and then picking the kth smallest. This brute-force approach is simple but inefficient for large tables (since m and n can be up to 30,000). The memory and time required to hold and sort the whole table would be impractical.

Instead, notice that the multiplication table is sorted row-wise and column-wise, but not globally. The key insight is that for any number x, we can efficiently count how many numbers in the table are less than or equal to x (by iterating through rows and counting for each row). This allows us to use a binary search approach: we can search for the smallest number such that at least k numbers in the table are less than or equal to it.

This approach avoids building and sorting the entire table, and instead leverages properties of the multiplication table to count efficiently.

Solution Approach

We use a binary search to find the kth smallest number in the multiplication table.

1. Define the Search Range:
   • The smallest value in the table is 1 (1 x 1).
   • The largest value is m * n (m x n).
   • We perform binary search in the range [1, m * n].
2. Count Numbers ≤ x:
   • For a given x, for each row i, the number of elements in that row ≤ x is min(x // i, n).
   • Sum this for all rows to get the count of numbers in the table ≤ x.
3. Binary Search Logic:
   • For each mid-value, count how many numbers are ≤ mid.
   • If the count is less than k, the answer must be larger, so move the left boundary up.
   • If the count is at least k, the answer could be mid or smaller, so move the right boundary down.
4. Termination:
   • When left == right, we've found the smallest number such that at least k numbers are ≤ it; this is our answer.

This approach is efficient because counting is O(m) per binary search step, and the search space is up to m*n.

Example Walkthrough

Let's walk through the example with m = 3, n = 3, k = 5.

• Initial Range: left = 1, right = 9
• First Iteration:
  • mid = (1 + 9) // 2 = 5
  • Count numbers ≤ 5:
    • Row 1: min(5 // 1, 3) = 3
    • Row 2: min(5 // 2, 3) = 2
    • Row 3: min(5 // 3, 3) = 1
    • Total = 3 + 2 + 1 = 6
  • 6 >= 5, so set right = 5
• Second Iteration:
  • mid = (1 + 5) // 2 = 3
  • Count numbers ≤ 3:
    • Row 1: min(3 // 1, 3) = 3
    • Row 2: min(3 // 2, 3) = 1
    • Row 3: min(3 // 3, 3) = 1
    • Total = 3 + 1 + 1 = 5
  • 5 >= 5, so set right = 3
• Third Iteration:
  • mid = (1 + 3) // 2 = 2
  • Count numbers ≤ 2:
    • Row 1: min(2 // 1, 3) = 2
    • Row 2: min(2 // 2, 3) = 1
    • Row 3: min(2 // 3, 3) = 0
    • Total = 2 + 1 + 0 = 3
  • 3 < 5, so set left = 3
• End: left = right = 3. The answer is 3.

Time and Space Complexity

• Brute-Force Approach:
  • Time: O(mn log(mn)), since we would generate all m * n elements and sort them.
  • Space: O(mn), to store all elements.
• Optimized (Binary Search) Approach:
  • Time: O(m log(mn))
    • Each binary search iteration costs O(m) to count numbers ≤ mid.
    • Number of binary search iterations is O(log(mn)).
  • Space: O(1), as we only use a constant amount of extra space.

Summary

The key insight to efficiently solve the "Kth Smallest Number in Multiplication Table" problem is to use binary search over the value range of the table, leveraging the ability to count how many numbers are less than or equal to a candidate value without generating the table. This approach is elegant, avoids unnecessary computation and memory usage, and is scalable to very large tables. By focusing on counting and binary search, we transform a seemingly brute-force problem into an efficient solution.