Kth Smallest Number in Multiplication Table

This is the most straightforward and intuitive approach. The idea is to physically construct the entire m x n multiplication table, store all its m * n values in a single list, sort this list, and then simply pick the k-th element from the sorted list.

• Create a list or an array to hold all the numbers from the multiplication table.
• Use nested loops, with the outer loop running from i = 1 to m and the inner loop from j = 1 to n.
• Inside the inner loop, calculate the product i * j and add it to the list.
• After the loops complete, the list will contain all m * n elements.
• Sort the list in ascending order.
• The k-th smallest element is the element at index k - 1 of the sorted list.

We begin by initializing a dynamic array or list. We then iterate through each row i from 1 to m and each column j from 1 to n, computing the product i * j and adding it to our list. Once all m * n products are generated and stored, we use a standard sorting algorithm to arrange them in non-decreasing order. Finally, the element at index k - 1 (since lists are 0-indexed) is our desired k-th smallest number.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int findKthNumber(int m, int n, int k) {
        List<Integer> table = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                table.add(i * j);
            }
        }
        Collections.sort(table);
        return table.get(k - 1);
    }
}