Solution: Kth Smallest Number in Multiplication Table

Statement

You are given a multiplication table of size m$\times$n, where each element at position mat[i][j] is calculated as $i \times j$ (with 1-based indexing).

Your task is to find the $k^{th}$ smallest element in this table, given the m, n, and k values.

Constraints:

• $1 \leq$ m, n $\leq 3 \times 10^4$

• $1 \leq$ k $\leq$ m $\times$n

Solution

We need to find the $k^{th}$ smallest number in a multiplication table of size $m \times n$, where the element at the position $(i, j)$ is the product $i \times j$. A direct approach to constructing the multiplication table and sorting the numbers would be inefficient. Instead of building the table explicitly, we can use the sorted properties of the multiplication table and binary search to find the $k^{th}$ smallest number.

The key intuition of this solution lies in two things:

• Ordered table: The numbers in the multiplication table are naturally ordered. The multiplication table has a specific structure: for each row $i$, the numbers are in the form $[i, 2\times i, 3 \times i, ..., n \times i]$, which are multiples of $i$.

• Counting elements: For any given value $x$, we can determine how many values in the table are less than or equal to $x$ by counting the elements in each row that satisfies this condition. For each row $i$, largest value in the $i^{th}$ row that is less than or equal to $x$ is at $x // i$ position in that row. However, the number of elements in the row is also bounded by $n$, so the count of values less than or equal to $x$ in the $i^{th}$ row is $min(x // i, n)$. By summing up these counts for all rows, we can determine if $x$ is a valid candidate for the $k^{th}$ smallest number in the table.

We use binary search and iterate over the range of possible values from $1$ to $m \times n$, to find the smallest value for which there are at least $k$ values less than or equal to it. By adjusting the search bounds based on the count of values, we converge on the $k^{th}$ smallest number without explicitly constructing the entire multiplication table.

Now, let’s look at the solution steps below:

1. We implement a function IsEnough(x) that calculates how many numbers in the multiplication table are less than or equal to x by summing up the counts across all rows.

2. We then initialize binary search bounds:

   1. low = 1 (the smallest possible value)

   2. high = m * n (the largest possible value in the table)

3. Next, we perform a binary search as long as low is less than high:

   1. Calculate the midpoint mid = (low + high) / 2. This midpoint is our current candidate for the $k^{th}$ smallest number.

   2. Check if enough(mid) returns TRUE (i.e., at least k numbers are less than or equal to mid).

      1. If it is, we set the upper bound to high = mid (as we search for the smallest valid mid).

      2. Otherwise, it means we need a larger number, so we update the lower bound to low = mid + 1.

4. We return low when low equals high, representing the $k^{th}$ smallest number.

Let’s look at the following illustration to get a better understanding of the solution: