Kth Smallest Number In Multiplication Table - Leetcode Solution

Problem Statement:

The multiplication table is a n x m table, where cell (i,j) contains the value of i * j (1-indexed). Given integers n and m, and an integer k, return the kth smallest number in the multiplication table.

Example 1: Input: n = 3, m = 3, k = 5 Output: 3 Explanation: The multiplication table is: 1 2 3 2 4 6 3 6 9 The 5th smallest number is 3 (1, 2, 2, 3, 3).

Example 2: Input: n = 2, m = 3, k = 6 Output: 6 Explanation: The multiplication table is: 1 2 3 2 4 6 The 6th smallest number is 6 (1, 2, 2, 3, 4, 6).

Approach:

To solve this problem, we can use binary search to find the kth smallest number in the multiplication table.

For each row i, we can find the number of elements smaller than or equal to k: min(k/i, m). For example, if k = 8 and i = 3, we can see that the largest j such that i*j <= k is j = 2, so there are 2 elements in row 3 that are smaller than or equal to k. We can add up the counts for each row to get the total number of elements less than or equal to k.

If the total count is less than or equal to k, we know that the kth smallest number is greater than or equal to the largest number in the multiplication table, n*m. If the total count is greater than k, we can use binary search to find the kth smallest number.

We can maintain a variable left = 1 (the smallest number in the table) and right = n*m (the largest number in the table). We then calculate the middle element, mid = (left+right)/2. We then count the number of elements in the multiplication table that are less than or equal to mid using the approach above.

If the total count is less than k, we know that the kth smallest number is greater than mid, so we update left = mid+1. If the total count is greater than or equal to k, we know that the kth smallest number is less than or equal to mid, so we update right = mid.

We repeat the above steps until left and right converge to the kth smallest number.

Code:

Here's the code that implements the above approach:

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

Time Complexity:

The time complexity of this approach is O(nlog(nm)), where n is the number of rows in the multiplication table and m is the number of columns in the multiplication table. We perform a binary search over the range [1,nm], and for each mid value, we count the number of elements in the multiplication table that are less than or equal to mid, which takes O(n) time. The binary search takes O(log(nm)) time, so the overall time complexity is O(nlog(nm)).

1