Kth Smallest Number in Multiplication Table

Kth Smallest Number in Multiplication Table

1. What is this problem about?

The Kth Smallest Number in Multiplication Table interview question asks you to find the $k^{th}$ smallest integer in an $m imes n$ table where table[i][j] = i * j. The values in the table are between $1$ and $m imes n$. Because the table can be $30,000 imes 30,000$, you cannot build or sort it.

2. Why is this asked in interviews?

Companies like Google and Uber ask this to test your ability to perform Binary Search on the answer space. It tests whether you can use a mathematical shortcut to count how many numbers are less than $X$ in a multiplication table in $O(M)$ time. It evaluation your Binary Search interview pattern proficiency.

3. Algorithmic pattern used

This follows the Binary Search on Value pattern.

1. Range: The answer is between 1 and $m imes n$.
2. Counting Function: For a given value $X$, how many numbers in the table are $\leq X$?
   • In row $i$, the numbers are $i, 2i, 3i, \dots, ni$.
   • The number of elements $\leq X$ in row $i$ is min(X / i, n).
   • Total count is sum(min(X / i, n)) for all $i$ from 1 to $m$.
3. Binary Search: Use this function to find the smallest $X$ such that count(X) >= k.

4. Example explanation

$m=3, n=3, k=5$. Table:

1 2 3
2 4 6
3 6 9

Sorted: 1, 2, 2, 3, 3, 4, 6, 6, 9. $k=5$ is 3.

• Range [1, 9]. Try mid = 4.
• Count $\leq 4$:
  • row 1: min(4/1, 3) = 3.
  • row 2: min(4/2, 3) = 2.
  • row 3: min(4/3, 3) = 1.
• Total = 6. Since $6 \geq 5$, 4 is a candidate. Try smaller.

5. Common mistakes candidates make

• Linear approach: Trying to iterate through the table ($O(M \cdot N)$).
• Off-by-one: Mistakes in the binary search boundaries or the count(X) >= k logic.
• Integer overflow: Forgetting that $m imes n$ can exceed $2^{31}-1$.

6. Interview preparation tip

Binary Search on the answer is the secret to almost all "Kth something in a virtual matrix" problems. Whenever you can't build the dataset, check if you can easily "count elements less than $X$."