Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have solved the problem of finding the K-th Smallest Number in Multiplication Table. This involve the concept of Binary Search.

PROBLEM STATEMENT

Suppose we have an m x n matrix named mat, which represents the multiplication table of integers from 1 to m and 1 to n. The element at row i and column j in mat is the product of i and j.

Given three positive integers m, n, and k, find and return the kth smallest element in the matrix mat.

EXAMPLE

Example 1:
Input: m = 2, n = 3, k = 6
Output: 6
Explanation:
The multiplication table is as follows:
1 2 3
2 4 6

The 6th smallest number in this table is 6.

Example 2:
Input: m = 5, n = 5, k = 10
Output: 12
Explanation:
The multiplication table is as follows:
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25

The 10th smallest number in this table is 12.

Approach

To find the k-th smallest number in an m x n Multiplication Table, we can apply a binary search on the range [1, mn].

At each step, we calculate the number of elements in the table that are less than or equal to the middle element of the range. We can do this by counting the number of elements in each row that are less than or equal to the middle element, and summing up these counts.

If the total count is less than k, we can discard the lower half of the range; otherwise, we discard the upper half. We repeat this process until the range is reduced to a single element, which is the k-th smallest number.

Brute Force Approach

Intuition
The brute force approach for finding the k-th smallest number in an m x n Multiplication Table involves generating the entire multiplication table and then sorting the elements in ascending order. Once the elements are sorted, we can directly access the k-th smallest number in constant time.
However, this approach is highly inefficient since it requires generating and sorting m x n elements, which can be prohibitively large for large values of m and n. Thus, the brute force approach is not practical for solving this problem.

Algorithm

Create an empty list to store the elements of the multiplication table.
Use nested loops to generate the elements of the multiplication table by multiplying each number from 1 to m by each number from 1 to n. Append each element to the list.
Sort the list in ascending order.
Return the k-th element of the sorted list.

Implemented Code

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int[] products = new int[m * n];
        int x = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                products[x++] = i * j;
            }
        }
        Arrays.sort(products);
        return products[k - 1];
    }
}

Time complexity O(mnlog(mn))
Space complexity O(mn)

Code Explained
We first first initialize an array called "products" with a length of m * n, which will hold all the products in the multiplication table. The variable "x" is used as an index for the "products" array.

Then, two nested loops are used to populate the "products" array with all the products in the multiplication table. The outer loop iterates over the rows of the table (from 1 to m), and the inner loop iterates over the columns (from 1 to n). The product of the current row and column is calculated and added to the "products" array at the current index (x), which is then incremented.

After all the products have been added to the "products" array, the array is sorted using the Arrays.sort() method. Finally, the k-th smallest number in the sorted "products" array is returned by accessing the (k-1)th index of the array, since array indices start at 0.

As an example, suppose we want to find the 3rd smallest number in a multiplication table of size 3 x 4. We call the function with arguments m=3, n=4, and k=3.

The "products" array is initialized with length 12, and the two nested loops populate it with the products of each cell in the table, in row-major order:
products[0] = 1x1 = 1
products[1] = 1x2 = 2
products[2] = 1x3 = 3
products[3] = 1x4 = 4
products[4] = 2x1 = 2
products[5] = 2x2 = 4
products[6] = 2x3 = 6
products[7] = 2x4 = 8
products[8] = 3x1 = 3
products[9] = 3x2 = 6
products[10] = 3x3 = 9
products[11] = 3x4 = 12

The "products" array is then sorted in ascending order:
[1, 2, 2, 3, 4, 6, 6, 8, 9, 12]

The 3rd smallest number is the number at the (k-1)th index, which is products[2] = 2. Therefore, the function returns 2 as the solution to the problem.

Binary Search Approach

Intuition
The intuition behind the algorithm is to perform a binary search on the range [1, mn], and at each step calculate the number of elements in the table that are less than or equal to the middle element of the range.

We can do this by counting the number of elements in each row that are less than or equal to the middle element, and summing up these counts.

Algorithm

Initialize low to 1 and high to m*n.
While low <= high:
Calculate mid as the average of low and high, rounded down to the nearest integer.
Initialize count to 0.
each row i from 1 to m:
Add min(n, floor(mid/i)) to count, where floor() is the floor division operator. d. If count < k, set low to mid + 1. e. Otherwise, set high to mid - 1.
Return low.

Implemented Code

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int l=1;
        int r=m*n;
        while(l<=r){
            int mid=l+(r-l)/2;
            int count = getCount(m,n,mid);
            if(count<k) l=mid+1;
            else r=mid-1;
        }
        return l;
    }

    private int getCount(int m, int n, int target){
        int count =0;
        for(int i=1;i<=m;i++){
            count+=Math.min(target/i,n);
        }
        return count;
    }
}

Time Complexity: O(mlog(mn))
Space Complexity: O(n)

Code Explained
The binary search algorithm maintains a range of possible values for the k-th smallest number. Initially, the range is from 1 to m*n, since these are the smallest and largest values in the multiplication table. Then, the algorithm repeatedly divides the range in half and checks whether the mid-point value is the k-th smallest number or not.

The "getCount" function is used to count the number of values in the multiplication table that are less than or equal to the mid-point value. This count is used to determine whether the mid-point value is too large or too small.

If the count is less than k, then we know that the k-th smallest number must be larger than the mid-point value. Therefore, we update the lower bound of the range to mid+1 and continue the binary search. Otherwise, if the count is greater than or equal to k, we know that the k-th smallest number must be smaller than or equal to the mid-point value. Therefore, we update the upper bound of the range to mid-1 and continue the binary search.

The binary search continues until the lower bound is greater than the upper bound, at which point we know that the current lower bound is the k-th smallest number.

As an example, suppose we want to find the 3rd smallest number in a multiplication table of size 3 x 4. We call the function with arguments m=3, n=4, and k=3.

Initially, the range is from 1 to 12, since these are the smallest and largest values in the multiplication table.

The first mid-point value is (1+12)/2 = 6. The "getCount" function returns 8, since there are 8 values in the table that are less than or equal to 6:

1 2 3 4 5 6
2 4 6 8 8 8
3 6 9 12 12 12

The count is greater than k=3, so we update the upper bound of the range to mid-1=5, and the new range is (1,5).

The next mid-point value is (1+5)/2 = 3. The "getCount" function returns 4, since there are 4 values in the table that are less than or equal to 3:

1 2 3
2 4 6
3 6 9

The count is less than k=3, so we update the lower bound of the range to mid+1=4, and the new range is (4,5).

The final mid-point value is (4+5)/2 = 4. The "getCount" function returns 6, since there are 6 values in the table that are less than or equal to 4:

1 2 3 4
2 4 6 8
3 6 9 12

The count is greater than k=3, so we update the upper bound of the range to mid-1=3.

At this point, the lower bound is equal to the upper bound, and we know that the k-th smallest number is l=4. Therefore, the function returns 4 as the solution to the problem.

Conclusion

In this article at OpenGenus, we have solved the problem "Find K-th Smallest Pair Distance" by understanding brute force and optimising it to get to the binary search solution.